DP(动态规划)【2】 最大连续子列和 最长不降子序列

1.最大连续子列和

#include 
#include 
#include 
#include 
#include 
#include 
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;iscanf("%d",&f[i]);
//一定要以i结尾！！ 
dp[0]=f[0];
int ans=f[0];
	for(int i=1;i
	{
	dp[i]=max(f[i],dp[i-1]+f[i]);
	if(dp[i]>ans) ans=dp[i];
	}
//	for(int i=1;i
 
printf("%d",ans);
}

 输出最大方案

这样写是不对的，只在dp[i]>ans才更新ans_i，举个例子

1，-2,0.5，1

导致ans_i=0

#include 
#include 
#include 
#include 
#include 
#include 
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;iscanf("%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
	{
	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
 
printf("%d %d %d",ans,ans_i+1,ans_j+1);
}

由于少了一句话一直在错，加上就对了

#include 
#include 
#include 
#include 
#include 
#include 
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;iscanf("%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
	{
		
		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
 
printf("%d %d %d",ans,ans_i2+1,ans_j+1);
}

答案

用了一个数组存储以i为结尾的start

#include 
#include 
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 
#include 
#include 
#include 
#include 
#include 
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;iscanf("%d",&f[i]);
//一定要以i结尾！！ 
dp[0]=1;
int temp=1;
int ans=1;
	for(int i=1;i
	{temp=1;
		for(int j=0;j
		{if(f[i]>=f[j])
		{
			if(dp[j]+1>temp){temp=dp[j]+1;//dp[i]=temp;
			}
		}
		}
		dp[i]=temp;
		if(ans
		
	}
//	for(int i=1;i
 
printf("%d",ans);
}

写完发现，temp其实是多余的）

输出最大方案

#include 
#include 
#include 
#include 
#include 
#include 
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;iscanf("%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
	{temp=1;
		for(int j=0;j
		{if(f[i]>=f[j])
		{
			if(dp[j]+1>temp){temp=dp[j]+1;anslist[i]=j;
			}
		}
		}
		dp[i]=temp;
		if(ans
		{		ans=temp;lst=i;//寻址 
		
 
		}
		
	}
//	for(int i=1;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(" ");
 
}
 
}