1.最大连续子列和
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾！！
dp[0]=f[0];
int ans=f[0];for(int i=1;i<n;i++){dp[i]=max(f[i],dp[i-1]+f[i]);if(dp[i]>ans) ans=dp[i];}
// for(int i=1;i<n;i++)printf("%d",ans);
}输出最大方案
这样写是不对的，只在dp[i]>ans才更新ans_i，举个例子
1，-2,0.5，1
导致ans_i=0
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾！！
dp[0]=f[0];
int ans=f[0];
int ans_i=0;
int ans_j=0;for(int i=1;i<n;i++){dp[i]=max(f[i],dp[i-1]+f[i]);if(dp[i]>ans){ans=dp[i];ans_j=i;if(dp[i-1]<0) ans_i=i;} }
// for(int i=1;i<n;i++)printf("%d %d %d",ans,ans_i+1,ans_j+1);
}由于少了一句话一直在错，加上就对了
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾！！
dp[0]=f[0];
int ans=f[0];
int ans_i=0;
int ans_j=0;
int ans_i2=0;for(int i=1;i<n;i++){if(dp[i-1]<0){ans_i=i;dp[i]=f[i];if(dp[i]>ans){ans=dp[i];ans_i2=ans_i;ans_j=i;}}else{dp[i]=f[i]+dp[i-1];if(dp[i]>ans){ans=dp[i];ans_j=i;ans_i2=ans_i;//就缺这句话！}}
}
// dp[i]=max(f[i],dp[i-1]+f[i]);
// if(dp[i]>ans)
// {
// ans=dp[i];ans_j=i;
// if(dp[i-1]<0) ans_i=i;
// }
// }
// for(int i=1;i<n;i++)printf("%d %d %d",ans,ans_i2+1,ans_j+1);
}答案
用了一个数组存储以i为结尾的start
#include <cstdio>
#include <algorithm>
using namespace std;const int MAXN = 10000;
int a[MAXN];
int dp[MAXN], start[MAXN];int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}dp[0] = a[0];start[0] = 0;for (int i = 1; i < n; i++) {if (dp[i - 1] >= 0) {dp[i] = dp[i - 1] + a[i];start[i] = start[i - 1];} else {dp[i] = a[i];start[i] = i;}}int k = 0;for (int i = 1; i < n; i++) {if (dp[i] > dp[k]) {k = i;}}printf("%d %d %d", dp[k], start[k] + 1, k + 1);return 0;
}难点：如何设计状态与状态转移方程
本题
状态 取：以第i位结尾的连续子序列最大和
2.最长不降子序列
如果要用枚举，复杂度2^n
状态：以第i个数结尾的序列长度dp[i]
状态转移方程：
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾！！
dp[0]=1;
int temp=1;
int ans=1;for(int i=1;i<n;i++){temp=1;for(int j=0;j<i;j++){if(f[i]>=f[j]){if(dp[j]+1>temp){temp=dp[j]+1;//dp[i]=temp;}}}dp[i]=temp;if(ans<temp) ans=temp;}
// for(int i=1;i<n;i++)printf("%d",ans);
}写完发现，temp其实是多余的）
输出最大方案
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾！！
dp[0]=1;
int temp=1;
int ans=1;
//int l=0,r=0;
int anslist[n]={0};
int lst=0;for(int i=1;i<n;i++){temp=1;for(int j=0;j<i;j++){if(f[i]>=f[j]){if(dp[j]+1>temp){temp=dp[j]+1;anslist[i]=j;}}}dp[i]=temp;if(ans<temp) { ans=temp;lst=i;//寻址 }}
// for(int i=1;i<n;i++)//printf("%d",dp[i]);
printf("%d\n",ans);
int p[n];int k=0,t=lst;
p[0]=f[lst];
while(t>0)
{//k++;
if(anslist[t]==0)
{if(p[k]>=f[0])
{k++;t=anslist[t];p[k]=f[t];
}
else t=0;}
else
{k++;
t=anslist[t];
p[k]=f[t];
}}
for(int i=k;i>=0;i--)
{printf("%d",p[i]); if(i>0) printf(" ");}}
