真棒又是一道动规……讨厌……

题目描述

给出一段序列，选出其中连续且非空的一段使得这段和最大。

样例

样例输入
7
2 -4 3 -1 2 -4 3


样例输出
4

再经典不过的DP题了……
设$f_i$为从$a_1$到$a_i$的最大子段和。
则递推式：
$f_i=max(a_i,f_i-1+a_i)$
所以接下来是WA……$AC$代码：

#include <bits/stdc++.h>
using namespace std;
int a[200010], f[200010], n;
int main() {
    scanf("%d", &n); 
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1;i <= n; i++) f[i] = -100000;
    for (int i = 1;i <= n; i++) f[i] = max(a[i], f[i - 1] + a[i]);
    int ans = -100000;
    for (int i = 1;i <= n; i++) ans = max(ans, f[i]);
    printf("%d", ans);
    return 0;
}

注意这道题很坑……有负数

呵呵……能搞个专门发拼团链接的栏目吗？
（感觉分享栏题解栏问答栏还有首页……链接满天飞……）

#include <bits/stdc++.h>
using namespace std;
int t, n, a, b;
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &a, &b);
        if (a + b >= n) printf("%d\n", n - a);
        else printf("%d\n", b + 1);
    }
    return 0;
}

可能是负数……害我调了好几遍

$$数字三角形$$

这道题和这道题有点像
这是一道经典DP题
这个也是一样：
对于$a_{x,y}$，只能从$a_{x-1,y}$和$a_{x-1,y-1}$转移而来。
所以状态转移方程就是：$f_{x,y}=max(f_{x-1,y},f_{x-1,y-1})+a_{x,y}$。

还要注意有个坑点：就是数值有可能是负数。

代码：（还是边读入边处理）

#include <bits/stdc++.h>
using namespace std;
int n, a[510][510];
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++)
        for (int j = 0;j <= n + 1; j++) a[i][j] = -10000000; //两边也要设为负数。
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= i; j++) {
            scanf("%d", &a[i][j]);
            a[i][j] += max(a[i - 1][j], a[i - 1][j - 1]);
        }
    int ans = -10000000;
    for (int i = 1;i <= n; i++) ans = max(ans, a[n][i]);  //统计ans
    printf("%d\n", ans);
    return 0;
}

$$摘花生$$

首先，我们知道，对于每一个点，它只能从上面或左边转移而来。
那么，对于这一个点，我们当然会选取上面和左边中价值最大的进行转移。
所以，我们可以设定一个二维数组：int f[110][110]，存储从$a_{1,1}$到$a_{x,y}$的最大价值。
状态转移方程就是：$f_{x,y}=max(f_{x-1,y},f_{x,y-1})+a_{x,y}$
最后献上代码：（我的代码没有开$f$数组，是边读入边处理的，直接在$a$数组上进行修改）

#include <bits/stdc++.h>
using namespace std;
int T, a[110][110], n, m;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1;i <= n; i++)
            for (int j = 1;j <= m; j++) {
                scanf ("%d", &a[i][j]);
                a[i][j] += max(a[i - 1][j], a[i][j - 1]);
            }
        printf("%d\n", a[n][m]);
    }
    return 0;
}

运行时间$336ms$