重新开始慢慢写题作为练习，考虑到我本身在动态规划的算法上面比较弱，先从dp开始练起
第一道题就emmmm没想得特别明白其实 题目大意是给n个数，要你选择m段互补相交的段让它们的和最大
dp[i][j]表示前j个数里分成i段的话最大值是多少，这里有一个隐含的意思是此时第j个数一定被分到了第i段里，那么更新公式有$dp[i][j]=max(dp[i][j-1]+a[j],max(dp[i-1][k]+a[j])(0\leq k\leq j-1))$，第一种表示在第i段最后添加第j个数，第二种表示找到前i-1段的情况下最大值而后将第j个数作为新的一段的开始，但是如果每次我们都要搜一遍前j个数来找最大值的话显然复杂度是会爆掉的，所以我们需要想想办法，实际上，在更新的过程中，我们实际上就隐含的确定了$max(dp[i][k]+a[j])(0\leq k\leq j)=dp[i][j]$，所以我们本轮更新的结果是可以记录下来到下一轮来使用的，这样可以把时间复杂度缩到O(mn),空间上实际上dp[i][j]只与上一轮相关，所以不需要存如此多的轮次，只需要存一个轮次而后渐次更新即可。
++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[1000030],number[1000030],maxm[1000030];
const int INF=0x3fffffff;
int main(){
int m,n;
while(~scanf("%d%d",&m,&n)){
memset(dp,0,sizeof(dp));
memset(maxm,0,sizeof(maxm));
for(int i=1;i<=n;++i){
scanf("%d",&number[i]);
}
int lastmaxm=-INF;
for(int i=1;i<=m;++i){
lastmaxm=-INF;
for(int j=i;j<=n;++j){
dp[j]=max(dp[j-1]+number[j],maxm[j-1]+number[j]);
maxm[j-1]=lastmaxm;
lastmaxm=max(lastmaxm,dp[j]);
}
}
printf("%d\n",lastmaxm);
}
return 0;
}
|