总目录详见：https://blog.csdn.net/mrcrack/article/details/86501716
信息学奥赛一本通（C++版） 第二部分 基础算法 第九章 动态规划
第一节 动态规划的基本模型
//1258 【例9.2】数字金字塔
//动态规划，自底向上计算，找出当前节点的最大值，一步一步推到顶点2017-11-3 21:57
#include <stdio.h>
int a[1100][1100],sum[1100][1100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for(j=1;j<=n;j++)sum[n][j]=a[n][j];
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
sum[i][j]=max(sum[i+1][j]+a[i][j],sum[i+1][j+1]+a[i][j]);
printf("%d",sum[1][1]);
return 0;
}
//1259 【例9.3】求最长不下降序列
//提交，未通过，测试点3 答案错误
//上了题目的大当,不下降序列,两个元素值相等也属于不下降序列，
//但从题意来说两个元素相等不属下降序列，认识到这个问题，花了20分钟
//按相等也属序列来处理，修改，提交AC 2017-11-3 23:03
#include <stdio.h>
int b[210],d[210],a[210];
int main(){
int n,i,j,max=-999999999,k,q=0,m;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&b[i]);
for(i=1;i<=n;i++){
d[i]=1;
for(j=1;j<i;j++)
if(b[j]<=b[i]&&d[j]+1>d[i])d[i]=d[j]+1;//此处写成if(b[j]<b[i]&&d[j]+1>d[i])d[i]=d[j]+1;
if(d[i]>max)max=d[i],k=i;
}
m=max;
a[q++]=k,i=k-1;
while(m>1){//根据d[i]值逆向查找，
if(d[i]==m-1&&b[i]<=b[k])a[q++]=i,k=i,m--;//此处写成 if(d[i]==m-1&&b[i]<b[k])a[q++]=i,k=i,m--;
i--;
}
printf("max=%d\n",max);
for(i=q-1;i>=0;i--)
printf("%d ",b[a[i]]);
return 0;
}
方法二
#include <stdio.h>
int pre[210],b[210],d[210],a[210];
void print(int k){
if(k==-1)return;
print(pre[k]);
printf("%d ",b[k]);
}
int main(){
int n,i,j,max=-999999999,k,q=0,m;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&b[i]);
for(i=1;i<=n;i++)pre[i]=-1;
for(i=1;i<=n;i++){
d[i]=1;
for(j=1;j<i;j++)
if(b[j]<=b[i]&&d[j]+1>d[i])pre[i]=j,d[i]=d[j]+1;//此处写成if(b[j]<b[i]&&d[j]+1>d[i])d[i]=d[j]+1;
if(d[i]>max)max=d[i],k=i;
}
m=max;
printf("max=%d\n",max);
print(k);
return 0;
}
//1260 【例9.4】拦截导弹(Noip1999)
//用之前洛谷p1020 导弹拦截 http://blog.csdn.net/mrcrack/article/details/61625530 AC代码提交，竟然测试点6答案错误，惊愕
//a[]导弹数 b[]最长下降子序列 拦截系统 c[]最长上升子序列
//加上等于，提交，测试点3,8答案错误，这下放心，测试点6安全通过，
//仔细想了想，最少能拦截1枚导弹，最少需要一套系统，故mx=-1错误
//提供一组测试样例
//输入：
//123
//输出：
//1
//1
//修改，提交，测试点3答案错误
//突然想到一组测试数据
//输入：
//1 1 1 1 1
//输出：
//5
//1
//修改，提交AC，该题的数据确实比洛谷要精进许多。
#include <stdio.h>
int a[1100],b[1100],c[1100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int cnt=0,i,j,mx=1;//此处写成mx=-1
while(scanf("%d",&a[cnt++])!=EOF)
for(i=0;i<cnt;i++){
b[i]=1;
for(j=0;j<i;j++)
if(a[j]>=a[i]&&b[j]+1>b[i])//通过测试点6 if(a[j]>=a[i]&&b[j]+1>b[i]) 注意等号不能省
b[i]=b[j]+1;
mx=max(mx,b[i]);
}
printf("%d\n",mx);
mx=1;//此处写成mx=-1
for(i=0;i<cnt;i++){
c[i]=1;
for(j=0;j<i;j++)
if(a[j]<a[i]&&c[j]+1>c[i])//再次测试，发现此处if(a[j]<=a[i]&&c[j]+1>c[i])，要通过测试点3，必须将=号去除//通过测试点6 if(a[j]<=a[i]&&c[j]+1>c[i]) 注意等号不能省
c[i]=c[j]+1;
mx=max(mx,c[i]);
}
printf("%d\n",mx);
return 0;
}
//1261 【例9.5】城市交通路网
//很想用Dijkstra 或是 floyd算法，但看到题目要求，想想还是算了
//翻看了一些代码，发现就是Dijkstra算法，想想也是，要是能很快想出的算法，也就不需要研究了。
//决定用Dijkstra算法，采用邻接表方式，也算是一个挑战吧。
//有向图，打印途经路径遇到困难，
//打印路径，http://blog.csdn.net/yuanba_xs/article/details/54799157参考该文，看了代码，很快就有感觉了。
//修改代码，提交AC 2017-11-4
//https://wenku.baidu.com/view/0ab0456883d049649a66588a.html 此文介绍得不错，摘抄如下：
//抽空进行研究。
#include <stdio.h>
#include <string.h>
#define INF 999999999
int cnt=0,head[1000],n,d[1000],vis[1000],path[1000],pre[1000];
struct node{
int to,next,w;
}e[10000];
void add_edge(int u,int v,int w){
cnt++,e[cnt].to=v,e[cnt].w=w,e[cnt].next=head[u],head[u]=cnt;
}
void print(int k){//递归打印路径
if(k==-1)return;
print(pre[k]);
printf("%d ",k+1);
}
int main(){
int i,j,w,b,t,k,v,min,q=0,x;//b边
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++){
scanf("%d",&w);
if(w)add_edge(i,j,w);
}
for(i=0;i<n;i++)d[i]=INF;
d[0]=0,t=n-1,vis[0]=1,pre[0]=-1;
for(b=head[0];b;b=e[b].next)d[e[b].to]=e[b].w;
while(t--){//一个点查询一次
min=INF;
for(i=0;i<n;i++)
if(vis[i]==0&&d[i]<min)min=d[i],k=i;
vis[k]=1;
for(b=head[k];b;b=e[b].next){
v=e[b].to,w=e[b].w;//漏了该句 w=e[b].w 查了好久
if(vis[v]==0&&d[v]>d[k]+w)d[v]=d[k]+w,pre[v]=k;
}
}
printf("minlong=%d\n",d[n-1]);
k=n-1;
print(k);
return 0;
}
//1262 【例9.6】挖地雷
//本想深度优先遍历，发现n<=200，暂放弃。
//画图模拟了一下，发现是一维线性动态规划。
//样例通过，提交AC，太佩服自己了，此题独立思考，编写，提交AC，没有参考任何资料，（期间一度想看看他人代码，忍住了），水平就是这样提高的
//2017-11-25 15:15
#include <stdio.h>
#include <string.h>
int a[210][210],w[210],d[210],pre[210];//d[i]表示挖到i点的最大值
void print(int k){
if(k==0)return;
print(pre[k]);
if(pre[k]==0)printf("%d",k);
else printf("-%d",k);
}
int main(){
int i,j,n,max=0,k;
memset(a,0,sizeof(a)),memset(pre,0,sizeof(pre));
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&w[i]);
while(scanf("%d%d",&i,&j)&&i&&j){
a[i][j]=1;//有向图
}
for(i=1;i<=n;i++)d[i]=w[i];
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
if(a[j][i]&&d[j]+w[i]>d[i])//此处写成if(a[j][i]&&d[j]+w[j]>d[i])眼高手低//请注意，有向图,j->i
d[i]=d[j]+w[i],pre[i]=j;//此处写成 d[i]=d[j]+w[j];
if(d[i]>max)max=d[i],k=i;
}
print(k);
printf("\n%d",max);
return 0;
}
//1263 【例9.7】友好城市
//该题破题很难，觉得手足无措
//瞟了一眼http://blog.csdn.net/ruruoran/article/details/38533337看到
//先以南岸排升序。处理数据时用求最长上升子序列的方法，就没再往下看了
//模拟了样例，立马有了思路。
//看了数据范围，N<=5000，冒泡排序应该可以接受，选择原因是代码容易写
//样例通过，提交AC,害怕的TLE没有出现
#include <stdio.h>
struct node{
int a,b;
}q[5100],q_t;
int d[5100];//北岸 最长上升子序列
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j,mx=-1;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&q[i].a,&q[i].b);
for(i=1;i<=n;i++)//南岸自小到大排序，若相等，北岸自小到大排序
for(j=i+1;j<=n;j++)
if(q[i].a>q[j].a)
q_t=q[i],q[i]=q[j],q[j]=q_t;
else if(q[i].a==q[j].a)
if(q[i].b>q[j].b)
q_t=q[i],q[i]=q[j],q[j]=q_t;
for(i=1;i<=n;i++){
d[i]=1;
for(j=1;j<i;j++)
if(q[j].b<=q[i].b&&d[j]+1>d[i])
d[i]=d[j]+1;
mx=max(mx,d[i]);//此处写成mx=(mx,d[i]);，查了半天，真是犯晕了
}
printf("%d",mx);
return 0;
}
//1264 【例9.8】合唱队形
http://blog.csdn.net/mrcrack/article/details/61625530
2.//p1091 合唱队形
NOIP 2004 提高组 复赛 chorus 合唱队形
1.读完题目，可以理解为处理最长上升子序列，最长下降子序列。
2.上述思路闪过后，开始模拟样例，看看能不能整合思路。
3.顺序的上升子序列，逆序的上升子序列。
4.模拟了样例，如下：
5.思路如上，顺序上升，逆序上升，对应位置求和，找出最大值，总数-最大值+1即为答案。
6.开始编码。样例测试通过，提交AC。一次性成功。
附上AC代码，编译环境Dev-C++4.9.9.2
#include <stdio.h>
int a[100+10],b[100+10],c[100+10];
int max=1;
int main(){
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++){//顺序，最长上升子序列
b[i]=1;
for(j=1;j<i;j++)
if(a[j]<a[i]){
if(b[j]+1>b[i])
b[i]=b[j]+1;
}
}
for(i=n;i>=1;i--){//逆序，最长上升子序列
c[i]=1;
for(j=n;j>i;j--)
if(a[j]<a[i])
if(c[j]+1>c[i])
c[i]=c[j]+1;
}
for(i=1;i<=n;i++)
if(max<b[i]+c[i])
max=b[i]+c[i];
printf("%d\n",n-max+1);
}
2017-4-22 15:10
//1265【例9.9】最长公共子序列 2018-3-14
#include <stdio.h>
#include <string.h>
char a[1010],b[1010];
int f[1010][1010];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,j,len_a,len_b;
scanf("%s%s",&a[1],&b[1]);
len_a=strlen(&a[1]),len_b=strlen(&b[1]);
for(i=0;i<=len_a;i++)f[i][0]=0;
for(i=0;i<=len_b;i++)f[0][i]=0;
for(i=1;i<=len_a;i++)
for(j=1;j<=len_b;j++)
if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
printf("%d",f[len_a][len_b]);
return 0;
}
//1265 【例9.9】最长公共子序列
//题目，感受，题目内容书写太烦，最好能改成让人更喜欢读，倾向于下面网站所写的书中内容的描述
//样例通过，提交AC
//此题更详细的解法可以参考http://blog.csdn.net/mrcrack/article/details/78437385
//11.3 最长公共子序列
//ALDS1_10_C:Longest Common Subsequence
#include <stdio.h>
#include <string.h>
int f[210][210];//f[i][j]字符串1 取i个元素 字符串2 取j个元素 对应的最长公共子序列长度
char a[210],b[210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,j,len_1,len_2;
a[0]=' ',b[0]=' ';
scanf("%s%s",a+1,b+1);
len_1=strlen(a)-1,len_2=strlen(b)-1;//扣除开始的' '
for(i=1;i<=len_1;i++)f[i][0]=0;
for(j=1;j<=len_2;j++)f[0][j]=0;
for(i=1;i<=len_1;i++)
for(j=1;j<=len_2;j++){
if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;//此处写成 if(a[i]==b[i])f[i][j]=f[i-1][j-1]+1;低级错误
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}
printf("%d",f[len_1][len_2]);
return 0;
}
//1266 【例9.10】机器分配
//http://blog.csdn.net/xy20130630/article/details/51753142此文代码写得够短，内容写得够简洁
//看了里面的公式，发现本人的想法还是差了一点点，不过，进步可喜。
//http://blog.csdn.net/xiaoxiaoluo/article/details/8037288此文打印公司及台数写得不错
//综上所述，解决问题，需要一个一个的来。
//采用对照代码的形式，发现问题，样例通过，提交AC。注意，该题，取最大值时，需要考虑=号
#include <stdio.h>
#include <string.h>
int f[15][20],a[15][20],out[15][20];//f[i][j]前i个公司，分配
void print(int x,int y){
if(x==0)return;
print(x-1,y-out[x][y]);
printf("%d %d\n",x,out[x][y]);//此处写成 printf("%d %d\n",x,y);
}
int main(){
int i,j,k,n,m;
memset(f,0,sizeof(f)),memset(a,0,sizeof(a)),memset(out,0,sizeof(out));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(k=0;k<=j;k++)//注意k的取值范围 ,之前写成for(k=1;k<=j;k++)
if(f[i][j]<=f[i-1][j-k]+a[i][k]){//此处写成if(f[i][j]<=f[i-1][k]+a[i][j-k])//注意，写成if(f[i][j]<f[i-1][k]+a[i][j-k]) 无法AC
f[i][j]=f[i-1][j-k]+a[i][k];
out[i][j]=k;//记录了3个关键信息i,j,k
}
printf("%d\n",f[n][m]);
print(n,m);
return 0;
}
//1281 最长上升子序列
//此题注意不能取等号
#include <stdio.h>
int d[1100],a[1100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j,mx=-1;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++){
d[i]=1;
for(j=1;j<i;j++)
if(a[j]<a[i]&&d[j]+1>d[i])//此处写成 if(a[j]<=a[i]&&d[j]+1>d[i])
d[i]=d[j]+1;
mx=max(mx,d[i]);
}
printf("%d",mx);
return 0;
}
//1282 最大子矩阵
//1224 最大子矩阵
#include <stdio.h>
#include <string.h>
int a[110][110],b[110],n;
int maxArray(int c[]){
int d=0,i,max=-999999999;
for(i=1;i<=n;i++){
if(d>0)d=d+c[i];
else d=c[i];
if(d>max)max=d;
}
return max;//此处写成 return d; 出昏招，查了25分钟
}
int main(){
int i,j,k,max=-999999999,t;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++){//矩阵扫描思路，1->n,2->n,3->n,4->n,......
memset(b,0,sizeof(b));
for(j=i;j<=n;j++){
for(k=1;k<=n;k++)
b[k]+=a[j][k];
t=maxArray(b);
if(t>max)max=t;
}
}
printf("%d",max);
return 0;
}
//https://www.cnblogs.com/GodA/p/5237061.html此文介绍得不错，摘抄如下，略做修改
//如果有一个一维数组a[n]，如何找出连续的一段，使其元素之和最大呢？
//例如有 1 2 -3 4 -2 5 -3 -1 7 4 -6 这样一个数组，那么显然 4 -2 5 -3 -1 7 4 这个子数组元素之和最大，为4+(-2)+5+(-3)+(-3)+7+4=14。为找到一维数组的最大子数组，我们可以有以下方法。
//输入数据：
11
1 2 -3 4 -2 5 -3 -1 7 4 -6
//输出数据：
14
//1.穷举法
#include <stdio.h>
int a[1000];
int main(){
int n,i,j,k,sum,max=-999999999;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++){
sum=0;
for(k=j;k<=i;k++)sum+=a[k];
if(sum>max)max=sum;
}
printf("%d",max);
return 0;
}
//2.带记忆的递推法 ,个人感觉方法应该叫前缀和
#include <stdio.h>
int a[1000],b[1000];//b[i]前缀和,i之前元素的和，包括i元素
int main(){
int n,i,j,k,sum,max=-999999999;
scanf("%d",&n);
b[0]=0;
for(i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=b[i-1]+a[i];
for(i=1;i<=n;i++)
for(j=0;j<i;j++){
sum=b[i]-b[j];
if(sum>max)max=sum;
}
printf("%d",max);
return 0;
}
//3动态规划
//我们来分析一下最优子结构，若想找到n个数的最大子段和，那么要找到n-1个数的最大子段和，这就出来了。我们用b[i]来表示a[0]...a[i]的最大子段和，b[i]无非有两种情况
//：(1)最大子段一直连续到a[i] (2)以a[i]为首的新的子段 。由此我们可以得到b[i]的状态转移方程：b[i]=max{b[i-1]+a[i],a[i]}。最终我们得到的最大子段和为max{b[i], 0<=i<n}， 算法如下：
#include <stdio.h>
int a[1000],b; //b[i]必须要选元素i，对应的最大字段和
int main(){
int n,i,j,k,sum,max=-999999999;
scanf("%d",&n);
b=0;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
if(b>0)b+=a[i];
else b=a[i];//b<=0
if(b>max)max=b;
}
printf("%d",max);
return 0;
}
//1283 登山
//正序 最长上升子序列，逆序 最长上升子序列 不考虑等号
//每个位置相加，取最大值
//样例通过，提交AC
#include <stdio.h>
int a[1100],b[1100],c[1100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j,mx=0;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++){
b[i]=1;
for(j=1;j<i;j++)
if(a[j]<a[i]&&b[j]+1>b[i])b[i]=b[j]+1;
}
for(i=n;i>=1;i--){
c[i]=1;
for(j=n;j>i;j--)
if(a[j]<a[i]&&c[j]+1>c[i])c[i]=c[j]+1;
}
for(i=1;i<=n;i++)
mx=max(mx,b[i]+c[i]-1);//b[i],c[i] i算了2次，故需-1
printf("%d",mx);
return 0;
}
//1284 摘花生
//动态规划公式：f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
//样例通过，提交AC
#include <stdio.h>
#include <string.h>
int f[110][110],a[110][110];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int t,r,c,i,j;
scanf("%d",&t);
while(t--){
memset(f,0,sizeof(f));
scanf("%d%d",&r,&c);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
printf("%d\n",f[r][c]);
}
return 0;
}
//1285 最大上升子序列和
#include <stdio.h>
int a[1100],sum[1100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j,mx=-1;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++){
sum[i]=a[i];
for(j=1;j<i;j++)
if(a[j]<a[i]&&sum[j]+a[i]>sum[i])
sum[i]=sum[j]+a[i];
mx=max(mx,sum[i]);
}
printf("%d",mx);
return 0;
}
//1286 怪盗基德的滑翔翼
#include <stdio.h>
int a[110],d[110],b[110];
int max(int a,int b){
return a>b?a:b;
}
int f(int a[],int n){
int i,j,mx_1=-1,mx_2=-1;
for(i=1;i<=n;i++){//顺序方向
d[i]=1;
for(j=1;j<i;j++)
if(a[j]>a[i]&&d[j]+1>d[i])
d[i]=d[j]+1;
mx_1=max(mx_1,d[i]);
}
for(i=n;i>=1;i--){//逆序方向
d[i]=1;
for(j=n;j>i;j--)
if(a[j]>a[i]&&d[j]+1>d[i])
d[i]=d[j]+1;
mx_2=max(mx_2,d[i]);
}
return max(mx_1,mx_2);
}
int main(){
int t,i,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
printf("%d\n",f(a,n));
}
return 0;
}
//1287 最低通行费
//一直被 "商人必须在(2N-1)个单位时间穿越出去" 这句所羁绊
//http://blog.csdn.net/snayf/article/details/70198261此文将困惑解决，摘抄如下：
//先看题目只能走（2n-1）步，不难看出只能向右和向下走，故设f[i][j]为到达（i,j）位上最省钱的花钱数，
//因只能向下与向右，故不难推出f[i][j]=min(f[i][j-1]+f[i-1][j])+a[i][j]。细节请看下面。
//看了上述文字后，代码就没往下看了，完全可以自己编了。
//该题同样，破题难啊。
//样例通过，提交未通过,测试点全部答案错误。
//将int 改成 long long,提交，未通过
//重新将long long 改成int
//使劲查啊查，发现该文代码与本人基本一致http://m.blog.csdn.net/C18854805113/article/details/70243534
//对照，发现没问题，突然发现问题所在， f[1][1]=a[1][1];//此句写成 f[1][1]=1;查了1个小时//漏了该句
//修改，提交AC 2017-11-8 21:15
#include <stdio.h>
int f[110][110],a[110][110];
int min(int a,int b){
return a>b?b:a;
}
int main(){
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
f[1][1]=a[1][1];//此句写成 f[1][1]=1;查了1个小时//漏了该句
for(i=2;i<=n;i++)f[i][1]=f[i-1][1]+a[i][1];//这样初始化不行for(i=1;i<=n;i++)f[i][1]=a[i][1];
for(j=2;j<=n;j++)f[1][j]=f[1][j-1]+a[1][j];//这样初始化不行for(j=1;j<=n;j++)f[1][j]=a[1][j];
for(i=2;i<=n;i++)
for(j=2;j<=n;j++)
f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
printf("%d",f[n][n]);
return 0;
}
//1288 三角形最佳路径问题
#include <stdio.h>
#include <string.h>
int a[110][110],d[110][110];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j;
memset(a,0,sizeof(a));
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for(i=n;i>=1;i--)
for(j=1;j<=i;j++)
d[i][j]=max(d[i+1][j]+a[i][j],d[i+1][j+1]+a[i][j]);
printf("%d",d[1][1]);
return 0;
}
//1289 拦截导弹
#include <stdio.h>
int d[20],a[20];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j,mx=-1;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++){
d[i]=1;
for(j=1;j<i;j++)
if(a[j]>=a[i]&&d[j]+1>d[i])
d[i]=d[j]+1;
mx=max(mx,d[i]);
}
printf("%d",mx);
return 0;
}
2017-11-25 15:15 AC 该节内容
第二节 背包问题
1267：【例9.11】01背包问题 更深入的讨论详见 01背包进阶
方法三
//1267：【例9.11】01背包问题
//在线测评地址http://ybt.ssoier.cn:8088/problem_show.php?pid=1267
//突然想到，01背包 就是 多重背包 个数 为1的形式
//马上编码,样例通过，提交AC。2018-12-9 10:08
//没想到，最后是 多重背包 统一了 完全背包 01背包。收获很大，完成了统一理论，但还有些地方需想想明白
#include <stdio.h>
#include <string.h>
int w[35],c[35],s[35],f[35][210];//s[i]表示物体i的个数
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j,k;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++){
scanf("%d%d",&w[i],&c[i]);
s[i]=1;
}
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(j<w[i])
f[i][j]=f[i-1][j];
else
for(k=0;k<=s[i];k++)
if(j>=k*w[i])
f[i][j]=max(f[i][j],f[i-1][j-k*w[i]]+k*c[i]);
printf("%d\n",f[n][m]);
return 0;
}
//1267 【例9.11】01背包问题
方法一：
//1267 【例9.11】01背包问题
//二维数组
#include <stdio.h>
#include <string.h>
int w[35],c[35],f[35][210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(j>=w[i])f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
else f[i][j]=f[i-1][j];
printf("%d",f[n][m]);
return 0;
}
方法二：
//1267 【例9.11】01背包问题
滚动数组
#include <stdio.h>
#include <string.h>
int w[35],c[35],f[2][210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++)
for(j=0;j<=m;j++){
f[i%2][j]=f[(i-1)%2][j];
if(j>=w[i])f[i%2][j]=max(f[(i-1)%2][j],f[(i-1)%2][j-w[i]]+c[i]);
}
printf("%d\n",f[n%2][m]);
return 0;
}
滚动数组
#include <stdio.h>
#include <string.h>
int w[35],c[35],f[2][210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j,k=0;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++){
k^=1;//特别注意此行，容易写错位置
for(j=0;j<=m;j++){
f[k][j]=f[k^1][j];
if(j>=w[i])f[k][j]=max(f[k^1][j],f[k^1][j-w[i]]+c[i]);
}
}
printf("%d\n",f[k][m]);
return 0;
} //一维数组
#include <stdio.h>
#include <string.h>
int w[35],c[35],f[210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++)
for(j=m;j>=0;j--)
if(j>=w[i])f[j]=max(f[j],f[j-w[i]]+c[i]);
printf("%d",f[m]);
return 0;
}
//1267 【例9.11】01背包问题
//f[i][j]选i个物体，j是重量 对应最大价值
//样例通过，提交，测试点3，9答案错误
//修改，详见代码，提交AC 2017-11-17
#include <stdio.h>
#include <string.h>
int f[40][210],w[40],c[40];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++)//此处写成 for(i=0;i<=n;i++),测试点3，9答案错误
for(j=0;j<=m;j++)
if(j>=w[i])f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
else f[i][j]=f[i-1][j];
printf("%d",f[n][m]);
return 0;
}
//以下代码，用途是打印01背包中，选中的物品。供读者进行深入学习。2019-12-13
#include <stdio.h>
#include <string.h>
int f[40][210],w[40],c[40],g[40][210];//g[][]记录选中的物品
void print(int x,int y){//打印选中的物品
if(x==0)return;
print(x-1,y-g[x][y]);
if(g[x][y])printf("%d\n",g[x][y]);
}
int main(){
int m,n,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++)
for(j=0;j<=m;j++){
f[i][j]=f[i-1][j];
if(j>=w[i]&&f[i][j]<f[i-1][j-w[i]]+c[i])f[i][j]=f[i-1][j-w[i]]+c[i],g[i][j]=i;
}
printf("%d\n",f[n][m]);
print(n,m);
return 0;
}
上述代码的输入输出数据情况如下：
Input:
10 4
2 1
3 3
4 5
7 9
Output:
12
2
3
4
1268：【例9.12】完全背包问题
该题的更详细讨论，详见从01背包进化到完全背包
//1268：【例9.12】完全背包问题
//在线测评地址http://ybt.ssoier.cn:8088/problem_show.php?pid=1268
//用 多重背包 处理 完全背包
//一直在想 完全背包 如何 统一 多重背包
//没想到，最后是 多重背包 统一了 完全背包
//完全背包 转化成 多重背包 关键是 算出匹配最大容积 的个数
//样例通过，提交AC。2018-12-8 22:41
//很高兴，在统一 完全背包 与 多重背包的道路上，进了一步。
#include <stdio.h>
#include <string.h>
int w[35],c[35],s[35],f[35][210];//s[i]匹配最大容积 的个数
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,j,k,m,n;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++){
scanf("%d%d",&w[i],&c[i]);
s[i]=m/w[i];
}
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(j<w[i])
f[i][j]=f[i-1][j];
else
for(k=0;k<=s[i];k++)
if(j>=k*w[i])
f[i][j]=max(f[i][j],f[i-1][j-k*w[i]]+k*c[i]);
printf("max=%d\n",f[n][m]);
return 0;
}
//1268 【例9.12】完全背包问题
//一般思路，样例通过，提交AC 2018-1-18
摘自 背包问题九讲 2018-12-5
以下代码能AC。2018-12-7
#include <stdio.h>
#include <string.h>
int w[40],c[40],f[40][210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,j,k,m,n;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(j<w[i])f[i][j]=f[i-1][j];
else
for(k=1;k*w[i]<=j;k++)
f[i][j]=max(f[i-1][j],f[i-1][j-k*w[i]]+k*c[i]);
printf("max=%d\n",f[n][m]);
return 0;
}以下代码也能AC。2018-12-7
#include <stdio.h>
#include <string.h>
int w[35],v[35],f[35][210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j,k;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(j<w[i])f[i][j]=f[i-1][j];
else for(k=1;k*w[i]<=j;k++)
f[i][j]=max(f[i-1][j],f[i][j-k*w[i]]+k*v[i]);//此处写成 f[i][j]=max(f[i][j],f[i][j-k*w[i]]+v[i]);
printf("max=%d",f[n][m]);
return 0;
}
//1268 【例9.12】完全背包问题
//等同于01背包的做法
//样例通过，提交，只有测试带点7,8答案正确
//参照http://blog.csdn.net/ruruoran/article/details/38615425进行修改
//要从数学模拟角度进行说明
//提交，AC 2017-11-18 10:38
#include <stdio.h>
#include <string.h>
int f[40][210],w[40],c[40];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(w[i]>j)f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i][j-w[i]]+c[i]);
printf("max=%d",f[n][m]);
return 0;
}
//1268 【例9.12】完全背包问题
//一维数组 2018-1-18 样例通过，提交AC
#include <stdio.h>
#include <string.h>
int w[35],v[35],f[210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j,k;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
for(i=1;i<=n;i++)
for(j=w[i];j<=m;j++)//此处写成 for(j=1;j<=m;j++)
f[j]=max(f[j],f[j-w[i]]+v[i]);//顺序更新，解释如下，因f[j-w[i]]需是最新数据，故必须从左往右更新，若从右往左更新，左边的数据是旧的，但右侧数据需要用最新的左侧数据，故右侧数据不对。理解这句花了好长时间，持续思考时间超过一个月，总算有收获。2018-1-18 请注意完全背包，需自左向右更新。
printf("max=%d",f[m]);
return 0;
}
1269 【例9.13】庆功会 更深入的讨论详见01背包进阶到多重背包
滚动数组，易于理解2019-12-25 21:48
//多重背包
#include <stdio.h>
int f[2][6010],v[505],w[505],s[505],n,m;
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,k,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d%d%d",&v[i],&w[i],&s[i]);
for(i=1;i<=n;i++)
for(k=0;k<=s[i];k++)
for(j=k*v[i];j<=m;j++)
f[i%2][j]=max(f[i%2][j],f[(i-1)%2][j-k*v[i]]+k*w[i]);//此处错写成f[i%2][j]=f[(i-1)%2][j],f[i%2][j]=max(f[i%2][j],f[(i-1)%2][j-k*v[i]]+k*w[i]);
printf("%d\n",f[n%2][m]);
return 0;
}//1269 【例9.13】庆功会
//多重背包。
//在线测评地址http://ybt.ssoier.cn:8088/problem_show.php?pid=1269
//采用完全背包写法，提交30分，百思不得其解，搜遍网络，没有满意的文章，铺天盖地一维数组写法
//而最接近思维的二维数组写法一直不得而见，无奈，只能从数据角度入手。
//以下为多重背包的完全背包写法，只有30分,提供给读者。2018-12-7
//提供一组测试数据
输入
5 10
6 59 9
5 62 0
7 46 9
1 21 5
5 15 1
输出
143
//发现问题，
//马上 for(k=0;k<=s[i]&&k*v[i]<=j;k++)//此处写成 for(k=1;k<=s[i]&&k*v[i]<=j;k++)
//继续测试数据，又发现问题
//感觉 for(k=0;k<=s[i]&&k*v[i]<=j;k++) 中的 &&k*v[i]<=j画蛇添足了
//仔细想了细节，f[i][j]一直在f[i-1][j],f[i][j], f[i-1][j-k*v[i]]+k*w[i]之间进行更新
//故 f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);//此处写成f[i][j]=max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i]);
//自个举的例子通过，提交AC.2018-12-7
//真不容易啊，耗去整整半天时间。 不过映像更深了。值，回头要将完全背包全部更新。
//以下为AC代码。
#include <stdio.h>
#include <string.h>
int v[510],w[510],s[510],f[510][6100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,m,i,j,k;
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d%d%d",&v[i],&w[i],&s[i]);
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(j<v[i])
f[i][j]=f[i-1][j];
else{
for(k=0;k<=s[i];k++)此处写成&&k*v[i]<=j画蛇添足了 for(k=1;k<=s[i]&&k*v[i]<=j;k++)
if(j>=k*v[i])
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);//此处写成f[i][j]=max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i]);
}
printf("%d\n",f[n][m]);
return 0;
}
//1269 【例9.13】庆功会
//多重背包。
//在线测评地址http://ybt.ssoier.cn:8088/problem_show.php?pid=1269
//采用完全背包写法，提交30分，百思不得其解，搜遍网络，没有满意的文章，铺天盖地一维数组写法
//而最接近思维的二维数组写法一直不得而见，无奈，只能从数据角度入手。
//以下为多重背包的完全背包写法，只有30分,提供给读者。2018-12-7
#include <stdio.h>
#include <string.h>
int v[510],w[510],s[510],f[510][6100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,m,i,j,k;
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d%d%d",&v[i],&w[i],&s[i]);
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(j<v[i])
f[i][j]=f[i-1][j];
else{
for(k=1;k<=s[i]&&k*v[i]<=j;k++)
f[i][j]=max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i]);
}
printf("%d\n",f[n][m]);
return 0;
}
//1269 【例9.13】庆功会
//http://blog.csdn.net/rechard_chen/article/details/38589803比较喜欢此文的思路，摘抄如下：
//这个题其实完全背包差不多的性质；只不过完全背包的物品的个数是无限的，而这一题是有限制的。
//采用一维数组，故从大到小开始处理
//样例通过，提交AC 2017-12-27
#include <stdio.h>
int v[510],w[510],s[510],f[6100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,m,i,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d%d%d",&v[i],&w[i],&s[i]);
for(i=1;i<=n;i++)
for(j=m;j>=0;j--)
for(k=0;k<=s[i];k++)
if(j-k*v[i]>=0)
f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
printf("%d",f[m]);
return 0;
}
//1270：【例9.14】混合背包
//在线测评地址http://ybt.ssoier.cn:8088/problem_show.php?pid=1270
//01背包 完全背包 均可 归结为 多重背包
//样例通过，提交AC。完成了统一。2018-12-10 12:40
#include <stdio.h>
#include <string.h>
int w[35],c[35],s[35],f[35][210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j,k;
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++){
scanf("%d%d%d",&w[i],&c[i],&s[i]);
if(s[i]==0)s[i]=m/w[i];//将 完全背包 转化为 多重背包
}
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
if(j<w[i])
f[i][j]=f[i-1][j];
else
for(k=0;k<=s[i];k++)
if(j>=k*w[i])
f[i][j]=max(f[i][j],f[i-1][j-k*w[i]]+k*c[i]);
printf("%d\n",f[n][m]);
return 0;
}
//1270 【例9.14】混合背包
//https://www.cnblogs.com/zzyh/p/6741123.html此文思路不错，摘抄如下：
//其实就是将三种背包合在了一起，加个if判断是怎么背包 再怎样做就可以了
//01背包是最基础的背包 容量V 价值 重量 求V范围内价值最大的
//多重背包是在01背包的基础上 只能取1件改成了能取多件
//完全背包则是取无限件
//01背包 和 多重背包是很像的
//注意如果 容量v逆序是01和多重 这样不会重复拿取产生矛盾
//顺序则是 完全背包了
//可惜，上述代码，提交，未通过
//一查题目，发现n<=30，m<=200,修改代码，提交AC
//采用一维数组
//样例通过，提交AC 2017-12-27
#include <stdio.h>
#include <string.h>
int w[40],c[40],p[40],f[210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int m,n,i,j,k;
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)scanf("%d%d%d",&w[i],&c[i],&p[i]);
for(i=1;i<=n;i++)
if(p[i]==0)//完全背包
for(j=w[i];j<=m;j++)//顺序
f[j]=max(f[j],f[j-w[i]]+c[i]);
else//01背包，多重背包
for(k=1;k<=p[i];k++)
for(j=m;j>=w[i];j--)//逆序
f[j]=max(f[j],f[j-w[i]]+c[i]);
printf("%d",f[m]);
return 0;
}
//1271 【例9.15】潜水员
//http://blog.csdn.net/hynu_zhizuzhe/article/details/38895781此文代码写得不错，需要进行修改
//采用降维的01背包
//样例通过，提交AC 2017-12-27 18:59
#include <stdio.h>
#include <string.h>
int a[1100],b[1100],c[1100],f[30][90];
int min(int a,int b){
return a<b?a:b;
}
int main(){
int m,n,cnt,k,i,j,u,v;
memset(f,127,sizeof(f));
f[0][0]=0;//此句不能漏
scanf("%d%d%d",&m,&n,&cnt);
for(i=1;i<=cnt;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(i=1;i<=cnt;i++)
for(j=m;j>=0;j--)
for(k=n;k>=0;k--){
u=j+a[i],v=k+b[i];
if(u>=m)u=m;
if(v>=n)v=n;
f[u][v]=min(f[u][v],f[j][k]+c[i]);
}
printf("%d",f[m][n]);
return 0;
}
//1272 【例9.16】分组背包
//https://www.cnblogs.com/z360/p/6366074.html此文思路不错，摘抄如下：
//这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。
//也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，
//则有f[k][v]=max{f[k-1][v]，f[k-1][v-w[i]]+c[i]|物品i属于第k组}。
//使用一维数组的伪代码如下：
//for 所有的组k for v=V..0
//for 所有的i属于组k
//f[v]=max{f[v],f[v-w[i]]+c[i]}
//注意这里的三层循环的顺序，
//“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外
//。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
//另外，显然可以对每组中的物品应用完全背包中“一个简单有效的优化”。
//http://www.cnblogs.com/zzyh/p/6749387.html此文代码写得不错
//样例通过，提交AC 2017-12-28
//若写成if(j<w)break; 测试点1,3答案错误 2018-1-25 18:38
//翻看http://ybt.ssoier.cn:8088/problem_show.php?pid=1272 测试数据，才弄白原因，原来给的数据未必是按规则出牌，提供一组测试数据以供参考
输入：
178 5 4
40 555 1
66 333 3
38 1594 3
173 1840 1
99 1186 1
if(j>=w)正确输出：
2780
if(j<w)break; 错误输出：
2149
经过一番跟踪，弄明白了，if(j<w[q])break; 错误原因，for(k=1;k<=a[i][0];k++){
q=a[i][k];//物品序号
W[q]未必是随q单调递减，break；之后，可能还存在数据j>=w[q],但因为break;的原因，之后数据再没有尝试的机会了。上述原因，整整跟踪了两个小时，总算明白了，if(j<w[q])break;算法没有问题，关键是数据不配合，若能保证w[q]随q单调递减即可。2018-1-25 21:50
#include <stdio.h>
#include <string.h>
int w[40],c[40],a[20][40],f[210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int v,n,t,i,j,k,p,q;
memset(a,0,sizeof(a));
scanf("%d%d%d",&v,&n,&t);
for(i=1;i<=n;i++){
scanf("%d%d%d",&w[i],&c[i],&p);
a[p][++a[p][0]]=i;//a[p][0]存储p组元素个数
}
for(i=1;i<=t;i++)
for(j=v;j>=0;j--)
for(k=1;k<=a[i][0];k++){
q=a[i][k];//物品序号
if(j>=w[q])f[j]=max(f[j],f[j-w[q]]+c[q]);
}
printf("%d",f[v]);
return 0;
}
//1273 【例9.17】货币系统
//http://blog.csdn.net/ruruoran/article/details/39503021此文代码写得不错，摘抄如下：
//类似于完全背包
//提交，测试点6,9,10答案错误，将int 改成long long 提交AC 2017-12-28
//开到a[1010],f[1010]测试点6 运行错误
#include <stdio.h>
#include <string.h>
int a[10010];
long long f[10010];
int main(){
int n,m,i,j;
scanf("%d%d",&n,&m);//漏了此句
memset(f,0,sizeof(f));
f[0]=1;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)
for(j=a[i];j<=m;j++)//完全背包要自小到大，此处写成 for(j=m;j>=a[i];j--)
f[j]+=f[j-a[i]];//此处写成 f[j]=max(f[j],f[j-a[i]]+1);
printf("%lld",f[m]);
return 0;
}
//1290 采药
//01背包
//方法一
//二维数组
#include <stdio.h>
#include <string.h>
int t[110],c[110],f[110][1100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int T,M,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&T,&M);
for(i=1;i<=M;i++)scanf("%d%d",&t[i],&c[i]);
for(i=1;i<=M;i++)
for(j=0;j<=T;j++)
if(j>=t[i])f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+c[i]);
else f[i][j]=f[i-1][j];
printf("%d",f[M][T]);
return 0;
}
//1290 采药
//01背包
//方法二
//一维数组
#include <stdio.h>
#include <string.h>
int t[110],c[110],f[1100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int T,M,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&T,&M);
for(i=1;i<=M;i++)scanf("%d%d",&t[i],&c[i]);
for(i=1;i<=M;i++)
for(j=T;j>=0;j--)
if(j>=t[i])f[j]=max(f[j],f[j-t[i]]+c[i]);
printf("%d",f[T]);
return 0;
}
//1290 采药
4.p1048 采药
NOIP 2005 普及组 复赛 medic 采药
1.样例比较简单，很快就模拟成功，该题是01背包问题。
2.很快编码成功，样例通过，提交10分，只对了测试点1。
3.一查，竟然是数组开得太小了，int f[100+10][1000+10];//1此处写成 f[100+10][100+10];修改提交AC。
附上AC代码，编译环境Dev-C++4.9.9.2
#include <stdio.h>
int t[100+10],v[100+10];
int f[100+10][1000+10];//1此处写成 f[100+10][100+10];
int fun(int a,int b){
if(a>b)
return a;
else
return b;
}
int main(){
int T,m,i,j;
scanf("%d%d",&T,&m);
for(i=1;i<=m;i++)
scanf("%d%d",&t[i],&v[i]);
for(i=0;i<=T;i++)
f[0][i]=0;
for(i=1;i<=m;i++)
for(j=0;j<=T;j++)
if(j<t[i])
f[i][j]=f[i-1][j];
else
f[i][j]=fun(f[i-1][j],f[i-1][j-t[i]]+v[i]);
printf("%d\n",f[m][T]);
}
4.优化空间
#include <stdio.h>
int t[100+10],v[100+10];
int f[1000+10];//1此处写成 f[100+10][100+10];
int fun(int a,int b){
if(a>b)
return a;
else
return b;
}
int main(){
int T,m,i,j;
scanf("%d%d",&T,&m);
for(i=1;i<=m;i++)
scanf("%d%d",&t[i],&v[i]);
for(i=0;i<=T;i++)
f[i]=0;
for(i=1;i<=m;i++)
for(j=T;j>=0;j--)//1此处写成 for(j=0;j<=T;j++)
if(j>=t[i])
f[j]=fun(f[j],f[j-t[i]]+v[i]);
printf("%d\n",f[T]);
}
//1291 数字组合
//01背包问题 变种，方案数，基本思路可从01背包开始。
//样例通过，提交AC 2017-12-17 19:28
#include <stdio.h>
#include <string.h>
int f[25][1100],a[25];//f[i][j]取前i个数，和为j的方案数
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,m,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]),f[i][a[i]]=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(j<a[i])f[i][j]+=f[i-1][j];//第i个数放不进
else f[i][j]+=f[i-1][j]+f[i-1][j-a[i]];//第i个数能放进，分成两类，f[i-1][j]一类不放，f[i-1][j-a[i]]另一类放 ,f[i][j]是本身的情况
printf("%d",f[n][m]);
return 0;
}
//1292 宠物小精灵之收服
//http://blog.csdn.net/kerskver/article/details/53856729此文介绍得不错
//http://blog.csdn.net/C20192419MYS/article/details/77893920?locationNum=3&fps=1此文介绍得不错 本人更偏爱此文思路及代码
//思路摘抄如下：
//题目解析
//这是一道简单的二维背包——“01”背包的升级版。这道题有两个限制条件：精灵球的数量和皮卡丘的血量。这就意味着我们存状态的数组需要3维——即g[i][j][k] 表示在前i个有j个精灵球并且皮卡丘的血量为k时，能够抓到的精灵的个数。其他的和“01”背包 一样，用一个结构体数组储存每个精灵所对应的数据。
//struct OP
//{
// int ball,V;
//}F[105];
//接下来就是递推DP，也就是3重for循环（不会超时），分别枚举——
//1.前i个精灵
//2.用j个精灵球
//3.能满足的皮卡丘的血量
//那么状态转移方程式是什么呢？首先设置g[i][j][k] 的最小值-假设皮卡丘的血量或精灵球的数量不足以抓住第i个精灵，则 g[i][j][k]=g[i-1][j][k]。而如果可以抓住，则考虑抓和不抓两种情况，取较大值，若抓，则为 g[i-1][j-F[i].ball][k-F[i].V]。
//别着急提交——交上去会 Time Limit Exceeded,但并不是因为作者的程序超时，而是测试机上的栈空间不够。
//还记得 “01”背包 的内存优化吗？二维背包也一样，第一维其实是可以省略的,但是就需要注意——枚举后两维时就需要逆序枚举了。
//样例通过，提交AC 2017-12-27
#include <stdio.h>
#include <string.h>
struct node{
int a,b;//a球数量，b体力伤害
}q[110];//此处写成 q[1100]
int f[1100][510];//此处写成f[510][110]
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,ball,value,i,j,k,ans=0;
memset(f,0,sizeof(f));
scanf("%d%d%d",&ball,&value,&n);//此处写成scanf("%d%d%d",&n,&ball,&value);
for(i=1;i<=n;i++)scanf("%d%d",&q[i].a,&q[i].b);
for(i=1;i<=n;i++)
for(j=ball;j>=0;j--)
for(k=value;k>=0;k--)
if(j>=q[i].a&&k>=q[i].b)
f[j][k]=max(f[j][k],f[j-q[i].a][k-q[i].b]+1);
for(i=1;i<=value;i++)
if(f[ball][i]==f[ball][value]){
ans=i;
break;
}
printf("%d %d",f[ball][value],value-ans);
return 0;
}
//1293 买书
//http://blog.csdn.net/clover_hxy/article/details/50151377此文代码写得不错
//完全背包的方案总数问题
//可以跟踪如下程序的f[i]，就能很快明白此种动态规划的写法
//样例通过，提交AC 2017-12-26 21:50
#include <stdio.h>
#include <string.h>
int f[1010],v[]={10,20,50,100};
int main(){
int n,i,j;
memset(f,0,sizeof(f));
scanf("%d",&n);
f[0]=1;
for(i=0;i<4;i++)
for(j=1;j<=n;j++)
if(j>=v[i])
f[j]+=f[j-v[i]];
printf("%d",f[n]);
return 0;
}
//1294 Charm Bracelet
//01背包问题，但要用一维数组来解决，否则超出内存限制
//样例通过，提交AC 2017-12-18 21:22
#include <stdio.h>
#include <string.h>
int w[3600],c[3600],f[13000];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,m,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
for(i=1;i<=n;i++)
for(j=m;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);//f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i])//不放 放
printf("%d",f[m]);
return 0;
}
//1295 装箱问题
//01背包
//方法一
//二维数组
#include <stdio.h>
#include <string.h>
int v[35],f[35][20100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int V,n,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&V,&n);
for(i=1;i<=n;i++)scanf("%d",&v[i]);
for(i=1;i<=n;i++)
for(j=0;j<=V;j++)
if(j>=v[i])f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]);
else f[i][j]=f[i-1][j];
printf("%d",V-f[n][V]);
return 0;
}
//1295 装箱问题
//01背包
//方法二
//一维数组
#include <stdio.h>
#include <string.h>
int v[35],f[20100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int V,n,i,j;
memset(f,0,sizeof(f));
scanf("%d%d",&V,&n);
for(i=1;i<=n;i++)scanf("%d",&v[i]);
for(i=1;i<=n;i++)
for(j=V;j>=0;j--)
if(j>=v[i])f[j]=max(f[j],f[j-v[i]]+v[i]);
printf("%d",V-f[V]);
return 0;
}
//1295 装箱问题
5.//p1049 装箱问题
NOIP 2001 普及组 复赛 装箱问题
1.一眼看出01背包问题。
2.剩下最小体积，可以看成装载最大体积，之后总体积扣除，即得答案。
3.样例很快通过，提交AC。
附上AC代码，编译环境Dev-C++4.9.9.2
#include <stdio.h>
int v[30+10];
int f[30+10][20000+10];
int fun(int a,int b){
if(a>b)
return a;
else
return b;
}
int main(){
int V,n,i,j;
scanf("%d%d",&V,&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
for(i=0;i<=V;i++)
f[0][i]=0;
for(i=1;i<=n;i++)
for(j=0;j<=V;j++)
if(j<v[i])
f[i][j]=f[i-1][j];
else
f[i][j]=fun(f[i-1][j],f[i-1][j-v[i]]+v[i]);
printf("%d\n",V-f[n][V]);
return 0;
}
4.空间优化，采用一维数组。
#include <stdio.h>
int v[30+10];
int f[20000+10];
int fun(int a,int b){
if(a>b)
return a;
else
return b;
}
int main(){
int V,n,i,j;
scanf("%d%d",&V,&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
for(i=0;i<=V;i++)
f[i]=0;
for(i=1;i<=n;i++)
for(j=V;j>=0;j--)
if(j>=v[i])
f[j]=fun(f[j],f[j-v[i]]+v[i]);
printf("%d\n",V-f[V]);
return 0;
}
//1296 开餐馆
//奇了怪，《信息学奥赛一本通(C++版)》，提供两个代码，参考程序1 AC 参考程序2 50分
//样例通过，提交答案错误，静态阅读代码，printf("%d\n",f[a[n]]);//此处写成printf("%d\n",f[n]);，有失水准
//样例未通过，静态检查代码， f[a[i]]=max(f[a[i-1]],f[a[m]]+f[a[i]]);//此处写成f[i]=max(f[a[i-1]],f[a[m]]+f[a[i]]);有失水准
//修改，提交AC 2018-1-3
#include <stdio.h>
#include <string.h>
int a[110],f[1000100];//a[]存储距离 f[]存储利润 f[i] 1-i 之间开餐馆 最多利润
int max(int a,int b){
return a>b?a:b;
}
int main(){
int t,i,j,n,k,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
a[0]=0,memset(f,0,sizeof(f));
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)scanf("%d",&f[a[i]]);
for(i=1;i<=n;i++){
m=i-1;
while(m>0&&a[i]-a[m]<=k)m--;
f[a[i]]=max(f[a[i-1]],f[a[m]]+f[a[i]]);//此处写成f[i]=max(f[a[i-1]],f[a[m]]+f[a[i]]);有失水准//类似01背包,f[a[i-1]] a[i]处不建餐馆，最大利润 ,f[a[m]]+f[a[i]] a[i]处建餐馆，最大利润
}
printf("%d\n",f[a[n]]);//此处写成printf("%d\n",f[n]);，有失水准
}
return 0;
}
2018-1-3 AC 该节内容
第三节 动态规划经典题
//1274 【例9.18】合并石子
//此类动态规划思想，元素量逐渐增加，递推，枚举
//http://blog.csdn.net/u011123263/article/details/25507705此文代码写得不错
//样例通过，提交AC 2017-12-26 18:57
#include <stdio.h>
#include <string.h>
#define INF 999999999
int sum[110],f[110][110];//f[i][j] i堆 与 j堆合并之后的最大值
int min(int a,int b){
return a<b?a:b;
}
int main(){
int n,i,j,k,a;
memset(f,127,sizeof(f));//f[][]=2139062143
scanf("%d",&n);
sum[0]=0;
for(i=1;i<=n;i++){
scanf("%d",&a);
sum[i]=sum[i-1]+a;//sum[i] 1-i元素之和
}
for(i=1;i<=n;i++)f[i][i]=0;
for(i=n;i>=1;i--)
for(j=i+1;j<=n;j++)
for(k=i;k<=j-1;k++)//此句最难写，可以根据下面的动态转移方程分析得出 //此处写成for(k=i+1;k<=j-1;k++) 查得有点久
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
printf("%d",f[1][n]);
return 0;
}
//1275 【例9.19】乘积最大
//http://blog.csdn.net/fine_rose/article/details/63685548此文介绍得不错，思路摘抄如下
//创建二维数组 f[][] ,用 f[i][j] 表示前 i 位数包含 j 个乘号所能达到的最大乘积
//将 i 从 2 到 n 枚举，表示分割为前i位数字
//对每一次分割再次将 a 从 1 到 min(i-1,k) 枚举，表示前 i 位中含有 a 个乘号
//将 b 从 a 到 i - 1 进行一次枚举，表示前 i 位中含有 a 个乘号，且最后一个乘号的位置在 b 处。那么当最后一个乘号在 b 处时最大值为前 b 位中含有 a - 1 个乘号的最大值乘上 b 处之后的数字
//因此得出了状态转移方程 f[i][a] = max(f[i][a] , f[b][a-1] * cut(b + 1,i))
//——（cut(b + 1,i) 表示 b + 1 到 i 位数字）
//样例通过，提交AC 2017-12-26
#include <stdio.h>
#include <string.h>
char in[20];
int f[20][10];//f[i][j] i个数之间，放j个乘号，对应的积的最大值
int cut(int left,int right){//返回left到right之间的整数值
int i,ans=0;
for(i=left;i<=right;i++)
ans*=10,ans+=in[i]-'0';
return ans;
}
int min(int a,int b){
return a<b?a:b;
}
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,k,i,a,b;
memset(f,0,sizeof(f));
scanf("%d%d%s",&n,&k,&in[1]);
for(i=1;i<=n;i++)f[i][0]=cut(1,i);//0个乘号
for(i=2;i<=n;i++)
for(a=1;a<=min(i-1,k);a++)//乘号个数
for(b=a;b<i;b++)//此句最难写
f[i][a]=max(f[i][a],f[b][a-1]*cut(b+1,i));
printf("%d",f[n][k]);
return 0;
}
//1276 【例9.20】编辑距离
//该题 与 1298 计算字符串距离 思路基本雷同
//https://www.cnblogs.com/ylyvictor/p/7791510.html此文思路写得不错，摘抄如下
//dp大法好【手动滑稽
//好了进入正题
//状态：f[i][j]记录ai与bj的最优编辑距离
//结果：f[m][n]，其中m、n分别是a、b的串长
//初值：b串空，要删a串长个字符；a串空，要插b串长个字符
//转移方程：当a[i]=b[j]时，f[i][j]=f[i-1][j-1]，否则，f[i][j]=min(f[i-1][j-1]+1,f[i][j-1]+1,f[i-1][j]+1)
//说明：f[i-1][j-1]+1：改a[i]为b[j]；
//f[i][j-1]+1：a[i]后插入b[j-1]；
//f[i-1][j]+1：删a[i]。
//PS：数组一定要开大点，不然会RE后几个点
//亲身经历qaq
//样例通过，提交,测试点5 答案错误，测试点6-10运行错误，看开题目中说的 字符串A和B的长度均小于200 是不对的
//马上更改， #define maxn 2100//该句写成 #define maxn 210 提交AC 2018-1-7 20:46
#include <stdio.h>
#include <string.h>
#define maxn 2100//该句写成 #define maxn 210
char a[maxn],b[maxn];
int f[maxn][maxn];//f[i][j] 1-i与1-j 最小编辑距离
int min(int a,int b){
return a<b?a:b;
}
int main(){
int i,j,n,m;
scanf("%s%s",a+1,b+1);//注意此处技巧，字符串从a[1]开始而不是a[0]开始
n=strlen(a+1),m=strlen(b+1),memset(f,0,sizeof(f));//请注意 获取 字符串长度技巧
for(i=1;i<=n;i++)f[i][0]=i;//删除a中i个元素，需i次
for(i=1;i<=m;i++)f[0][i]=i;//在a中添加i个元素，需i次
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i]==b[j])f[i][j]=f[i-1][j-1];//无需操作，故与之前相等
else f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;//f[i-1][j] 删除a中的i元素 f[i][j-1]将b中的j元素插到a[i]后 f[i-1][j-1] 将a[i]改成b[j]
printf("%d",f[n][m]);
return 0;
}
//1277 【例9.21】方格取数
//http://blog.csdn.net/yanyanwenmeng/article/details/77073629此文思路代码都写得很不错
//NOIP2000复赛 提高组 第四题
1. 设状态：f[i][j][h][k];//表示两条路同时走，第一条路径走到(i,j)时，第二条走到（h,k）时的最大数字和；
2. 初始状态：f[0][0][0][0]=0;
最终状态：f[n][n][n][n];
3. 状态转移方程：当i==h&&j==k时，f[i][j][h][k]=max{f[i-1][j][h-1][k],f[i][j-1][h][k-1],f[i-1][j][h][k-1],f[i][j-1][h-1][k])+a[i][j];//取上上，左左，上左，左上四个方向的最大值加上当前的值；
当i!=h&&j!=k时，f[i][j][h][k]=max{f[i-1][j][h-1][k],f[i][j-1][h][k-1],f[i-1][j][h][k-1],f[i][j-1][h-1][k])+a[i][j]+a[h][k];//取上上，左左，上左，左上四个方向的最大值加上两条路径当前的值；
//一个笔误，修改了一个多小时，样例通过，提交AC 2017-12-29
#include <stdio.h>
#include <string.h>
int a[15][15],f[15][15][15][15];//f[i][j][r][c];(i,j),(r,c)最大值
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,j,r,c,n,u,v,w,t1,t2;
scanf("%d",&n);
memset(a,0,sizeof(a)),memset(f,0,sizeof(f));
while(scanf("%d%d%d",&u,&v,&w)&&u&&v&&w)a[u][v]=w;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(r=1;r<=n;r++)
for(c=1;c<=n;c++){
t1=max(f[i-1][j][r-1][c],f[i-1][j][r][c-1]);
t2=max(f[i][j-1][r-1][c],f[i][j-1][r][c-1]);//此处写成 t1=max(f[i][j-1][r-1][c],f[i][j-1][r][c-1]);昏招尽出，查了一个多小时
f[i][j][r][c]=max(t1,t2)+a[i][j];//找 f[i-1][j][r-1][c] f[i-1][j][r][c-1] f[i][j-1][r-1][c] f[i][j-1][r][c-1]中的最大值，顺序可打乱
if(i!=r&&j!=c)f[i][j][r][c]+=a[r][c];
}
printf("%d",f[n][n][n][n]);
return 0;
}
//1278 【例9.22】复制书稿(book)
//http://blog.csdn.net/c20182030/article/details/53445204此文写得不错
//https://www.cnblogs.com/shamman/p/7295495.html此文写得不错
//http://blog.csdn.net/wasd6081058/article/details/7110084?locationNum=5&fps=1此文思路介绍得不错，摘抄如下
//动态规划就是在做最优的选择，那么我们先随便做上一次选择，看看会把问题转化成什么样子（其实就是把大问题转化成小题），以赋值书稿问题为例，n个人去复制m本书，就是划分嘛，但怎么样才是最优的呢？不知道！好，那么我先尝试选择一下，一个人完成k本和m-1个人完成n-k本，问题就转换成max{f(m-1,n-k),f(1,k)},好，f(1,k)我们是知道的，而f(m-1,n-k)就是子问题了，这个子结构是最优子结构我就不证明了，而动态规划要找到最优的解，那书的划分我们就要尝试所有的可能，因此外面一定要套循环，也就是在k的所有可能里面找到min，那么这个min就是解了。
//在解决这个问题的时候，刚入手我老是在划分第一个人的时候搞不清楚，老想这第一个人copy k本书也有可能在中间呀？就不知道怎么用动态规划来解决了，其实这完全包含在子问题里面嘛！我们要注意动态规划的解决，（应该是所有的递归）都是从顶到下的，这就意味它是有顺序的，我的这个问题就是不会找这种顺序。
//样例通过，提交AC 2018-1-6 21:34 动态规划，动态转移方程是关键。动态规划的学习 任重而道远
#include <stdio.h>
#include <string.h>
#define maxn 510
int a[maxn],b[maxn],sum[maxn],f[maxn][maxn],c[maxn][maxn];//a[i]第i本书页码 b[i]第i个人 复制页面数 sum[i] 1-i本书页码数 f[i][j] 1-i个人 复制 1-j本书 最短时间
int max(int a,int b){
return a>b?a:b;
}
int min(int a,int b){
return a<b?a:b;
}
int main(){
int i,j,k,m,n,max_num,t;
scanf("%d%d",&m,&n);//m本书 n个人
sum[0]=0,memset(f,127,sizeof(f)),memset(b,0,sizeof(b)),memset(c,0,sizeof(c));
for(i=1;i<=m;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
for(j=1;j<=m;j++)f[1][j]=sum[j];//一个人 复制 j本书
for(i=2;i<=n;i++)
for(j=1;j<=m;j++)
for(k=i-1;k<j;k++)
f[i][j]=min(f[i][j],max(f[i-1][k],sum[j]-sum[k]));//max(f[i-1][k],sum[j]-sum[k]) f[i][j]的时间由1-i中某个人的最大时间决定 //min(f[i][j],max(f[i-1][k],sum[j]-sum[k])) 在所有f[i][j]的可能结果中寻找最短时间
max_num=f[n][m],t=n;//采用贪心算法 计算抄写 书码
for(i=m;i>0;i--){
if(a[i]+b[t]>max_num)t--;
b[t]+=a[i],c[t][++c[t][0]]=i;//c[t][0]统计t人 复制的书 的数量 c[t][1]对应 t人复制书的最大序号 c[t][c[t][0]]对应 t人复制书的最小序号
}
for(i=1;i<=n;i++)printf("%d %d\n",c[i][c[i][0]],c[i][1]);
return 0;
}
//1279 【例9.23】橱窗布置(flower)
//http://blog.csdn.net/u012773338/article/details/38414445此文代码和思路都写得漂亮 可惜提交，测试点1-2,4-5,8-10答案错误
//https://www.cnblogs.com/zzyh/p/6682979.html?utm_source=itdadao&utm_medium=referral此文思路和代码都写得漂亮,代码提交AC
//动态规划转移方程难写，但变量初始化以及变量的范围更难
//一直测试样例未通过，输出结果如下
//23
//2 3 4
//跟踪程序，发现从题中拷贝的输入数据有误，有误数据如下：
//3 5
//7 23 –5 –24 16
//5 21 -4 10 23
//-21 5 -4 -20 20
//更正后数据如下，请仔细对照,在输入数据上，耗费了1个小时，跟踪了程序，才发现问题
//3 5
//7 23 -5 -24 16
//5 21 -4 10 23
//-21 5 -4 -20 20
//更正输入数据后，发现程序对样例的处理，没有问题，看来 http://ybt.ssoier.cn:8088/problem_show.php?pid=1279 要对该题输入数据进行重新 输入
//样例通过，提交AC 2018-1-9 收获，学会了变量边界计算。最优过程路径的打印，还需多练习。
#include <stdio.h>
#include <string.h>
#define INF 999999999
int b[110][110],a[110][110],c[110][110],d[110];//d[i]用来记录最优美学值时，f-(i-1)花所放 花瓶 位置 //c[i][j]记录i束花插在j个空瓶，对应最大美学值，i-1束花所放瓶子位置
int main(){
int f,v,i,j,k,max=-INF,pos;
scanf("%d%d",&f,&v);
for(i=1;i<=f;i++)
for(j=1;j<=v;j++)
scanf("%d",&a[i][j]);
memset(b,128,sizeof(b));
for(j=1;j<=v-(f-1);j++)b[1][j]=a[1][j];//一束花//v-(f-1)//剩下f-1束花，至少需要f-1个空瓶，至多留给1束花 v-(f-1)个空瓶
for(i=1;i<=f;i++)//i束花
for(j=i;j<=v-(f-i);j++)//i束花，至少需要空瓶i个，故j=i,剩下的f-i束花 至少空瓶f-i个 故 可给 i束花 支配的 空瓶 最多v-(f-i)个空瓶
for(k=i-1;k<=j-1;k++)//i-1束花至少需要i-1个空瓶，故k=i-1,因第i-1束花必须在第i束花的左边，故第i-1束花最远可放在j-1空瓶里
if(b[i][j]<b[i-1][k]+a[i][j])
b[i][j]=b[i-1][k]+a[i][j],c[i][j]=k;//c[i][j]记录i束花插在j个空瓶，对应最大美学值时，i-1束花所放瓶子位置
for(j=f;j<=v;j++)
if(b[f][j]>max)
max=b[f][j],pos=j;//因b[i][j]数据由上一层b[i-1][k]决定，故 最大值 未必出现在 b[f][v]; //pos记录 美学值 最大 对应的 最后一束 花的 位置
printf("%d\n",max);//此处写成printf("%d\n",b[f][v]);错误 因b[i][j]数据由上一层b[i-1][k]决定，故 最大值 未必出现在 b[f][v];
for(i=f;i>=1;i--)//从最后一束花开始遍历
d[f-(i-1)]=pos,pos=c[i][pos];//请注意 //c[i][j]记录i束花插在j个空瓶，对应最大美学值时，i-1束花所放瓶子位置 技巧
for(i=f;i>=1;i--)printf("%d ",d[i]);//逆序输出
return 0;
}
//1280 【例9.24】滑雪
2.//p1434 滑雪
http://blog.csdn.net/mrcrack/article/details/61625530
//难度：普及/提高-
//考点：输入，输出 ,深度优先遍历，记忆化搜索。
//适用：小学生
//注意：过大的数组要开到main函数的外面。
//提交：70分，早有预料，还是很满意的，至少深度优先搜索找最大步数，还是掌握得不错， 测试点3,5WA 测试点10 TLE
//int max=1;//3之前 int max=0;仔细想想第一个点就算一步。 修改此处过了测试点3,5
//测试点10 TLE，估计代码需要大改。
//采用剪枝，记忆化搜索，测试点10还是TLE
//if(step<d[r1][c1])//剪枝
// return;
// d[r1][c1]=step;//记忆
//为了通过测试点10，程序经历大改。
//去除了vis数组，与以往写法大有不同。因其数据，是按自大到小读取，并且采用记忆方式读取，故略去vis数组。
#include <stdio.h>
#include <string.h>
int a[100+10][100+10];
int d[100+10][100+10];
int r,c;
int next[][2]={{-1,0},{1,0},{0,-1},{0,1}};//上 下 左 右
int fun(int a,int b){
if(a>b)
return a;
else
return b;
}
int dfs(int step,int r1,int c1){
int i,j,nr,nc,t=1;//请注意，初始化t=1
if(d[r1][c1]>0)
return d[r1][c1];
for(i=0;i<4;i++){
nr=r1+next[i][0];
nc=c1+next[i][1];
if(nr>=1&&nr<=r&&nc>=1&&nc<=c&&a[r1][c1]>a[nr][nc]){//2此处写成a[r1][c1]>a[nr][nc]查了会
t=fun(t,dfs(step+1,nr,nc)+1);
}
}
d[r1][c1]=t;
return t;
}
int main(){
int i,j,max=1;
memset(d,0,sizeof(d));
scanf("%d%d",&r,&c);
for(i=1;i<=r;i++)//1漏写了读取数据的循环
for(j=1;j<=c;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++){
max=fun(max,dfs(1,i,j));//3此处写成 max=(max,dfs(1,i,j));查了会
}
printf("%d\n",max);
return 0;
}
//1297 公共子序列
//1265 【例9.9】最长公共子序列
//题目，感受，题目内容书写太烦，最好能改成让人更喜欢读，倾向于下面网站所写的书中内容的描述
//样例通过，提交AC
//此题更详细的解法可以参考http://blog.csdn.net/mrcrack/article/details/78437385
//11.3 最长公共子序列
//ALDS1_10_C:Longest Common Subsequence
//样例通过，提交AC 2017-12-28 21:19
#include <stdio.h>
#include <string.h>
int f[210][210];//f[i][j]字符串1 取i个元素 字符串2 取j个元素 对应的最长公共子序列长度
char a[210],b[210];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int i,j,len_1,len_2;
while(scanf("%s%s",a+1,b+1)!=EOF){
a[0]=' ',b[0]=' ';
len_1=strlen(a)-1,len_2=strlen(b)-1;//扣除开始的' '
for(i=1;i<=len_1;i++)f[i][0]=0;
for(j=1;j<=len_2;j++)f[0][j]=0;
for(i=1;i<=len_1;i++)
for(j=1;j<=len_2;j++){
if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;//此处写成 if(a[i]==b[i])f[i][j]=f[i-1][j-1]+1;低级错误
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}
printf("%d\n",f[len_1][len_2]);
}
return 0;
}
//1298 计算字符串距离
//http://blog.csdn.net/July_xunle/article/details/70290836此文介绍得不错，思路摘抄如下：
//1.f[i][j]代表a字符串前i个字符和b字符串前j个字符改动次数;
//2.当i等于0时，需要改动j次，j等于0时，需要改动i次，即f[0][j]=j,f[i][0]=i;
//3.当a[i]=b[j]时，不需要改动，即f[i][j]=f[i-1][j-1];
//4.当a[i]!=b[j]时，有三种改动方式：改成一样，删a[i]，删b[j]，即得f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i][j-1])+1;
//http://blog.csdn.net/just_young/article/details/43113327此文思路讲解不错，摘抄如下
这道题的时间限制是1秒，但处理的字符串长度可能达到1000，所以如果使用递归的话，则必然超时。因此，可采用动态规划的方法，构造一个二维数组，数组的“长”和“宽”分别是两个字符串的长度。
以题中的一个例子举例，字符串a=“jlknm”，b=“mnklj”，则可构造一个6×6的二维数组array，并将二维数组的第一行和第一列初始化为如下，因为一个空字符串和任意一个字符串的距离始终为该字符串的长度。
用两层for循环遍历两个字符串a、b（i和j从1开始取值），对比每一个字符a[i-1]和b[j-1]，若两个字符相等，即a[i-1] == b[j-1]，则不增加距离，因此对应的数组array[i][j]=array[i-1][j-1]；若两个字符不相等，则可删除a[i-1]这个字符、删除b[j-1]这个字符，或修改a[i-1]使它与b[i-1]相等。array[i][j]取这三种方法的最小值。选择修改，则array[i][j] = 1 + array[i-1][j-1]，若选择删除a[i-1]，则array[i][j] = 1 + array[i-1][j]，若选择删除b[i-1]，则array[i][j] = 1 + array[i][j-1]。运用这个方法，可将二维数组填满，如下图所示。
最后，取这个数组的最后一个元素4，即为答案。
//样例通过，提交AC 2017-12-31 22:51
//感觉代码写得挺别扭，字符数组与f[][]数组存在错位关系，马上进行修改,提交，样例通过2018-1-1 9:05
#include <stdio.h>
#include <string.h>
char a[1100],b[1100];//此处写成 char a[1100],b[1100],f[1100][1100];笔误坏事
int f[1100][1100];
int min(int a,int b){
return a<b?a:b;
}
int main(){
int n,i,j,lena,lenb;
scanf("%d",&n);
while(n--){
scanf("%s%s",a+1,b+1);//请注意此处技巧 2018-1-1
lena=strlen(a+1),lenb=strlen(b+1);//请注意此处技巧 2018-1-1
for(i=0;i<=lena;i++)f[i][0]=i;
for(j=0;j<=lenb;j++)f[0][j]=j;
for(i=1;i<=lena;i++)
for(j=1;j<=lenb;j++)
if(a[i]==b[j])f[i][j]=f[i-1][j-1];
else f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
printf("%d\n",f[lena][lenb]);
}
return 0;
}
//1299 糖果
//http://blog.csdn.net/clove_unique/article/details/50171355此文代码和思路都不错，思路摘抄如下：
//Dzx的选择是2+3+4+5=14，这样糖果总数是7的倍数，并且是总数最多的选择。
//这道题是背包的一个变形，背包的体积需要%一个数。
//刚开始的思路是写一个恰放入的背包，然后枚举一下，但是发现那样的话体积的最大值达到了10^8，无论是时间还是空间都无法承受。
//那么考虑一下优化。其实%已经给我们提供了一个思路，那就是把体积缩小到需要%的这个正整数。
//f[i][j]表示前i个物品体积%k为j的最优值，我们可以得到状态转移方程。注意每一次都要更新，因为每个数%k的值是不确定的。
//https://www.cnblogs.com/candy99/p/5828055.html此文代码写得最接近01背包
//样例通过，提交AC 该题还是不理解，在初始化上，要好好模拟数据生成过程。
//样例数据生成过程如下所示：
f[0][0]=0 f[0][6]=-999999999 a[1]=1 f[1][0]=0
f[0][1]=-999999999 f[0][0]=0 a[1]=1 f[1][1]=1
f[0][2]=-999999999 f[0][1]=-999999999 a[1]=1 f[1][2]=-999999998
f[0][3]=-999999999 f[0][2]=-999999999 a[1]=1 f[1][3]=-999999998
f[0][4]=-999999999 f[0][3]=-999999999 a[1]=1 f[1][4]=-999999998
f[0][5]=-999999999 f[0][4]=-999999999 a[1]=1 f[1][5]=-999999998
f[0][6]=-999999999 f[0][5]=-999999999 a[1]=1 f[1][6]=-999999998
f[1][0]=0 f[1][5]=-999999998 a[2]=2 f[2][0]=0
f[1][1]=1 f[1][6]=-999999998 a[2]=2 f[2][1]=1
f[1][2]=-999999998 f[1][0]=0 a[2]=2 f[2][2]=2
f[1][3]=-999999998 f[1][1]=1 a[2]=2 f[2][3]=3
f[1][4]=-999999998 f[1][2]=-999999998 a[2]=2 f[2][4]=-999999996
f[1][5]=-999999998 f[1][3]=-999999998 a[2]=2 f[2][5]=-999999996
f[1][6]=-999999998 f[1][4]=-999999998 a[2]=2 f[2][6]=-999999996
f[2][0]=0 f[2][4]=-999999996 a[3]=3 f[3][0]=0
f[2][1]=1 f[2][5]=-999999996 a[3]=3 f[3][1]=1
f[2][2]=2 f[2][6]=-999999996 a[3]=3 f[3][2]=2
f[2][3]=3 f[2][0]=0 a[3]=3 f[3][3]=3
f[2][4]=-999999996 f[2][1]=1 a[3]=3 f[3][4]=4
f[2][5]=-999999996 f[2][2]=2 a[3]=3 f[3][5]=5
f[2][6]=-999999996 f[2][3]=3 a[3]=3 f[3][6]=6
f[3][0]=0 f[3][3]=3 a[4]=4 f[4][0]=7
f[3][1]=1 f[3][4]=4 a[4]=4 f[4][1]=8
f[3][2]=2 f[3][5]=5 a[4]=4 f[4][2]=9
f[3][3]=3 f[3][6]=6 a[4]=4 f[4][3]=10
f[3][4]=4 f[3][0]=0 a[4]=4 f[4][4]=4
f[3][5]=5 f[3][1]=1 a[4]=4 f[4][5]=5
f[3][6]=6 f[3][2]=2 a[4]=4 f[4][6]=6
f[4][0]=7 f[4][2]=9 a[5]=5 f[5][0]=14
f[4][1]=8 f[4][3]=10 a[5]=5 f[5][1]=15
f[4][2]=9 f[4][4]=4 a[5]=5 f[5][2]=9
f[4][3]=10 f[4][5]=5 a[5]=5 f[5][3]=10
f[4][4]=4 f[4][6]=6 a[5]=5 f[5][4]=11
f[4][5]=5 f[4][0]=7 a[5]=5 f[5][5]=12
f[4][6]=6 f[4][1]=8 a[5]=5 f[5][6]=13
14
2018-1-4 21:10
#include <stdio.h>
#define INF 999999999//此处写成 #define INF -999999999
int a[110],f[110][110];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,k,i,j;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
f[0][0]=0;//漏了此句
for(j=1;j<k;j++)f[0][j]=-INF;//此处写成 for(j=0;j<k;j++)此种算法难在初始化
for(i=1;i<=n;i++)
for(j=0;j<k;j++)
f[i][j]=max(f[i-1][j],f[i-1][(k+j-a[i]%k)%k]+a[i]);//此处写成f[i][j]=max(f[i-1][j],f[i][(k+j-a[i]%k)%k]+a[i]);//不放，放
printf("%d",f[n][0]);
return 0;
}
//1300 鸡蛋的硬度
//https://www.cnblogs.com/CXCXCXC/p/4888383.html此文，思路代码都写得不错 ,思路摘抄如下：
//f[i][j]表示从第i层，用j个蛋尝试，所用得的最小次数，f[i][j]并不代表一定在第i层去扔，可以在1~i中任意一层扔下一个蛋，因此搞一个循环变量k，k从1~i，对于一个当前的k，这个鸡蛋扔下去有两种情况：碎和不碎。如果碎了，那此时只有j-1个蛋，要尝试1~k-1层，即是f[k-1][j-1]; 如果不碎，还有j个蛋，那么就要考虑k+1~i层，这等效于f[i-k][j]。所以f[i][j]=min(f[i][j],max(f[k-1][j-1],f[j-k][j])+1)。
//样例通过，提交AC 2017-12-29 22:30
//提供一组数据生成过程
//输入:10 2
//f[1][2]=1 f[0][1]=0 f[0][2]=0
f[2][2]=2 f[0][1]=0 f[1][2]=1
f[2][2]=2 f[1][1]=1 f[0][2]=0
f[3][2]=3 f[0][1]=0 f[2][2]=2
f[3][2]=3 f[1][1]=1 f[1][2]=1
f[3][2]=2 f[2][1]=2 f[0][2]=0
f[4][2]=4 f[0][1]=0 f[3][2]=2
f[4][2]=3 f[1][1]=1 f[2][2]=2
f[4][2]=3 f[2][1]=2 f[1][2]=1
f[4][2]=3 f[3][1]=3 f[0][2]=0
f[5][2]=5 f[0][1]=0 f[4][2]=3
f[5][2]=4 f[1][1]=1 f[3][2]=2
f[5][2]=3 f[2][1]=2 f[2][2]=2
f[5][2]=3 f[3][1]=3 f[1][2]=1
f[5][2]=3 f[4][1]=4 f[0][2]=0
f[6][2]=6 f[0][1]=0 f[5][2]=3
f[6][2]=4 f[1][1]=1 f[4][2]=3
f[6][2]=4 f[2][1]=2 f[3][2]=2
f[6][2]=3 f[3][1]=3 f[2][2]=2
f[6][2]=3 f[4][1]=4 f[1][2]=1
f[6][2]=3 f[5][1]=5 f[0][2]=0
f[7][2]=7 f[0][1]=0 f[6][2]=3
f[7][2]=4 f[1][1]=1 f[5][2]=3
f[7][2]=4 f[2][1]=2 f[4][2]=3
f[7][2]=4 f[3][1]=3 f[3][2]=2
f[7][2]=4 f[4][1]=4 f[2][2]=2
f[7][2]=4 f[5][1]=5 f[1][2]=1
f[7][2]=4 f[6][1]=6 f[0][2]=0
f[8][2]=8 f[0][1]=0 f[7][2]=4
f[8][2]=5 f[1][1]=1 f[6][2]=3
f[8][2]=4 f[2][1]=2 f[5][2]=3
f[8][2]=4 f[3][1]=3 f[4][2]=3
f[8][2]=4 f[4][1]=4 f[3][2]=2
f[8][2]=4 f[5][1]=5 f[2][2]=2
f[8][2]=4 f[6][1]=6 f[1][2]=1
f[8][2]=4 f[7][1]=7 f[0][2]=0
f[9][2]=9 f[0][1]=0 f[8][2]=4
f[9][2]=5 f[1][1]=1 f[7][2]=4
f[9][2]=5 f[2][1]=2 f[6][2]=3
f[9][2]=4 f[3][1]=3 f[5][2]=3
f[9][2]=4 f[4][1]=4 f[4][2]=3
f[9][2]=4 f[5][1]=5 f[3][2]=2
f[9][2]=4 f[6][1]=6 f[2][2]=2
f[9][2]=4 f[7][1]=7 f[1][2]=1
f[9][2]=4 f[8][1]=8 f[0][2]=0
f[10][2]=10 f[0][1]=0 f[9][2]=4
f[10][2]=5 f[1][1]=1 f[8][2]=4
f[10][2]=5 f[2][1]=2 f[7][2]=4
f[10][2]=5 f[3][1]=3 f[6][2]=3
f[10][2]=4 f[4][1]=4 f[5][2]=3
f[10][2]=4 f[5][1]=5 f[4][2]=3
f[10][2]=4 f[6][1]=6 f[3][2]=2
f[10][2]=4 f[7][1]=7 f[2][2]=2
f[10][2]=4 f[8][1]=8 f[1][2]=1
f[10][2]=4 f[9][1]=9 f[0][2]=0
2017-12-30 8:43
#include <stdio.h>
int f[110][20];
int max(int a,int b){
return a>b?a:b;
}
int min(int a,int b){
return a<b?a:b;
}
int main(){
int n,m,i,j,k;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f[i][j]=i;
for(i=1;i<=n;i++)
for(k=1;k<=i;k++)
for(j=2;j<=m;j++)
f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);//+1表示当前尝试
printf("%d\n",f[n][m]);
}
return 0;
}
//1301 大盗阿福
//https://www.cnblogs.com/zzyh/p/6683813.html此文介绍得不错，思路摘抄如下：
//DP求出每一个状态的最优值，f[i]为盗窃前i家店铺的最优值，那么f[n]就是盗窃前n家店铺的最优值；
//面临的每个抉择就是这个店铺盗还是不盗？那就从盗和不盗中选择一个最优值。
//盗：f[i-2]+a[i];为前i-2家店铺的最优值+现在盗的店铺；
//不盗：f[i-1]；就是前f[i-1]家店铺的最优值；
//最后输出f[n]；
//思路有些类似01背包
//样例通过，提交AC 2017-12-26 21:22
#include <stdio.h>
int a[100100],f[100100];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int t,i,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
f[0]=0,f[1]=a[1];
for(i=2;i<=n;i++)f[i]=max(f[i-1],f[i-2]+a[i]);
printf("%d\n",f[n]);
}
return 0;
}
//1302 股票买卖
//http://blog.csdn.net/jklcl/article/details/54933193此文代码写得不错，甚合心意
//样例通过，提交AC 2017-12-30 16:48
#include <stdio.h>
#define maxn 100100
int dp1[maxn],dp2[maxn],a[maxn];//dp1[i] 1->i第一次买卖 dp2[i] i->n 第二次买卖 因同一天可以多次买卖，故dp1[i] dp2[i]都可以取到i值
#define INF 999999999
int min(int a,int b){
return a<b?a:b;
}
int max(int a,int b){
return a>b?a:b;
}
int main(){
int t,n,i,min_t,max_t,ans;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
min_t=INF,max_t=-INF,dp1[0]=0,dp2[n+1]=0,ans=-INF;//此处写成 min_t=-INF,max_t=INF 大失水准
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++){//从左往右，左边找最小值，右边找最大值
min_t=min(min_t,a[i]);
dp1[i]=max(dp1[i-1],a[i]-min_t);
}
for(i=n;i>=1;i--){从右往左，左边找最小值，右边找最大值
max_t=max(max_t,a[i]);
dp2[i]=max(dp2[n+1],max_t-a[i]);
}
for(i=1;i<=n;i++)ans=max(ans,dp1[i]+dp2[i]);
printf("%d\n",ans);
}
return 0;
}
//1303 鸣人的影分身
//弄懂样例是关键
//https://www.cnblogs.com/zzyh/p/6685427.html此文介绍得不错，摘抄如下：
//【思路】相当于把m个相同的苹果放入n个盘子中的方法的个数
//就将就着这个问题写思路吧 m个克拉能量相当于m个苹果，n个分身相当于n个盘子；
//对放入的情况进行讨论
//（1）当n>m(即当盘子个数大于苹果个数时)
//一定有m-n个盘子空着 那么这种情况和把m个苹果放入m个盘子效果是一样的；
//（2）当n<=m时（即当盘子个数小于苹果数）
//分类讨论：
//1、至少有一个盘子是空的的时候 就相当于把m个苹果放入n-1盘子中
//2、当每个盘子都有的时候（每个盘子都有苹果了那么至少是一个吧）
//效果就是 f(m-n,n)，把每个盘子的苹果都拿出一个；、
//因为递归（1）是盘子数不断减少，所以当n==1时，return 1（只有一个盘子那就只有一种方法）
// （2）是苹果数不断减少，所以我们定义m==0时 return 1（有一种方法）；
//样例通过，提交AC 2017-12-28 21:08
#include <stdio.h>
int dp(int m,int n){
if(m==0||n==1)return 1;
if(m<n)return dp(m,m);
return dp(m,n-1)+dp(m-n,n);
}
int main(){
int t,m,n;
scanf("%d",&t);
while(t--){
scanf("%d%d",&m,&n);
printf("%d\n",dp(m,n));
}
}
//1304 数的划分
//http://blog.csdn.net/u011860483/article/details/43967651此文思路写得不错，摘抄如下：
// 根据本题要求，要将整数n划分为k部分，而且在不考虑顺序的情况下每种划分互不相同。
//在此可以把问题抽象为一下模型：
//有n个箱子，要把它们垒成k栋，可以假设箱子按某种满足该要求的方式已经摆好，现在从最底层每栋拿掉一个箱子，这样就只有两种情况：
//1）之前每栋箱子的数量都多于1，则拿掉箱子后总栋数不变，则之前排列n个箱子成k栋的情况数与之后排列n-k个箱子成k栋的情况数是一样的
//2）之前有一栋箱子的数量是1，则之前排列n个箱子成k栋的情况数与之后排列n-1个箱子成k-1栋的情况数相同
//于是得出递推方程dp[n][k]=dp[n-j][k]+dp[n-1][k-1];
//出口是：dp[i][1]=1;
//http://blog.csdn.net/cacyth/article/details/51168371此文代码写得不错
//样例通过，提交AC 2017-12-29 18:56
#include <stdio.h>
int f[10][210];
int main(){
int n,k,i,j;
scanf("%d%d",&n,&k);
f[0][0]=1;
for(i=1;i<=k;i++)
for(j=i;j<=n;j++)
f[i][j]=f[i][j-i]+f[i-1][j-1];//此处写成 f[i][j]=f[i][j-i]+f[i-1][j-i];
printf("%d",f[k][n]);
return 0;
}
//1305 Maximum sum
//http://blog.csdn.net/wangjian8006/article/details/7588345此文思路介绍得不错，摘抄如下：
//题目大意： 对于连续的整数和的串s1和s2，s1与s2不相交，使得s1+s2最大
//解题方法： DP。
// lt[i]代表以第i个元素结尾的串最大值
// rt[i]代表以第i个元素开头的串的最大值
// 那么设置一个rtm[i]代表取后i个元素之中最大连续子串的和
// 很显然，lt[i]=max(a[i],lt[i-1]+a[i]);
// rt[i]=max(a[i],rt[i+1]+a[i]);
// rtm[i]=max(rtm[i+1],rt[i]);
//此题与poj2593一模一样，但是要将MAXV改成10010就可以A了
//理解rtm[i]花了些时间，采用跟踪数据的办法，弄明白了，同时派生出了自己的ltm[i]
//样例通过，提交AC 2018-1-7 17:13
#include <stdio.h>
#define maxn 50100
int lt[maxn],ltm[maxn],rt[maxn],rtm[maxn],a[maxn];//lt[i] 以i元素结尾的值最大串 ltm[i] 1-i元素中 值最大串 rt[i] 以i元素开始的值最大串 rtm[i] i-n元素中 值最大串
int max(int a,int b){
return a>b?a:b;
}
int main(){
int t,n,i,ans;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
lt[1]=a[1],rt[n]=a[n],ltm[1]=a[1],rtm[n]=a[n],ans=a[1];//初始化
for(i=2;i<=n;i++)lt[i]=max(a[i],lt[i-1]+a[i]);//lt[i] 1-i中 必须选元素i的最大值
for(i=n-1;i>=1;i--)rt[i]=max(a[i],rt[i+1]+a[i]);//rt[i] i-n中 必须选元素i的最大值
for(i=2;i<=n;i++)ltm[i]=max(ltm[i-1],lt[i]);//ltm[i] 1-i中 串的最大值
for(i=n-1;i>=1;i--)rtm[i]=max(rtm[i+1],rt[i]);//rtm[i] i-n中 串的最大值
for(i=2;i<=n;i++)ans=max(ans,ltm[i-1]+rtm[i]);//ltm[i-1]+rtm[i] 1-(i-1) 与 i-n 两个串的和的最大值
printf("%d\n",ans);
}
return 0;
}
转载自原文链接, 如需删除请联系管理员。
原文链接：信息学奥赛一本通（C++版） 第二部分 基础算法 第九章 动态规划，转载请注明来源！