织梦搭建企业网站/微营销软件

P1004 方格取数
这两题基本上一样了，就是放歌取数要加上起始位置，这个算法不算（1,1）的起始位置，右下角的位置的量到是算上了。这个算法比较好理解，算是基础题了吧。
最近一个多星期一直在学dp，感觉学了好多，不知道吸收了多少，等这个阶段的题刷完了要总结一下。九月和十月差不多做了一百题了吧。

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int f[20][10][10];
int max4(int a,int b,int c,int d){if(b>a)a=b;if(c>a)a=c;if(d>a)a=d;return a;
}
int main()
{int n,m,i,j,k,a[10][10]={0},x,y;scanf("%d",&n);for(;;){scanf("%d %d",&x,&y);scanf("%d",&a[x][y]);if(x==0&&y==0) break;}  for(k=1;k<n+n;k++)for(i=1;i<=n&&i<=k;i++)for(j=1;j<=n&&j<=k;j++){if(i==1&&j==1) continue;f[k][i][j]=max4(f[k-1][i][j-1],f[k-1][i-1][j],f[k-1][i-1][j-1],f[k-1][i][j])+a[i][k-i+1]+a[j][k-j+1];if(i==j)f[k][i][j]-=a[i][k-i+1];}printf("%d",f[n+n-1][n][n]+a[1][1]);return 0;
}

P1006 传纸条

#include<stdio.h>
#include<string.h>
#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y
const int inf=0x3f3f3f3f;
int n,m,sum[1005],a[105][105],f[105][55][55];
int max4(int a,int b,int c,int d){if(b>a)a=b;if(c>a)a=c;if(d>a)a=d;return a;
}
int main()
{int i,j,ans=0,x,y,k;scanf("%d %d",&n,&m);for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]);for(k=2;k<m+n;k++)//坐标图上一条线两个点的x和y相加相等for(i=1;i<=n&&i<=k;i++)//i,j表示两个点所在的行数，k-i+1和k-j+1就表示纵坐标了for(j=1;j<=n&&j<=k;j++){if(i==1&&j==1) continue;f[k][i][j]=max4(f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1],f[k-1][i][j])+a[i][k-i+1]+a[j][k-j+1];if(i==j) f[k][i][j]-=a[i][k-i+1];//两条路径经过一个点只能被计算一次}printf("%d",f[n+m-1][n][n]);return 0;
}