hdu 2571 dp入门题
来源：程序员人生 发布时间：2015-05-20 10:34:47 阅读次数：2598次
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2571
常规dp，恰好让我这菜鸟来找找 找状态转移方程的感觉。。
定义dp[i][j] 表示的是第i行j列所具有的最大的荣幸值。
dp[i][j] 由3种情况转移而来：1、从上面1个坐标转移而来，即dp[i⑴][j] 。2、由左侧转移过来，即dp[i][j⑴]。3、由他同1行中的 j 的因数列转移过来的（但是要除j自己），即dp[i][ j 的因数列]
找出这3种情况中最大的就能够了，dp[i][j] += max(...)
我是这样处理的先找出因数列中最大的，并将其保存，这样就再转化成3者中最大的。
要特别注意的就是边界情况的处理，由于题目中说了可能有负数，那末对边界情况要进行特殊的讨论，由于0已不是最小的了，有可能会影响到最大值的肯定（比如全是负数，结果边界那里是0，反而被当作最大），如果是第1行的话只能从上述的2、3情况转移过来，如果是第1列，只能从1这类情况转移过来，dp[1][1]的话就是本身了。
看了discuss觉得很受启发，还可以将dp[][0] dp[0][] 都设为 -INF ，并且将dp[1][0] dp[0][1] 设为0 这样边界情况的时候就不会出现特殊的情况，不需要特殊讨论了。
代码+注释：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1009
#define INF 0x3f3f3f3f
int dp[M][M];
int main()
{
int n,m,t;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
//for(int i = 0;i <= n;i++) //也能够进行奇妙的处理边界旁的初始化使得边界情况不需要特殊斟酌
// dp[i][0] = -INF; //将边界旁的都设为-INF，使其不影响结果
//for(int i = 0;i <= m;i++)
//dp[0][i] = -INF;
//dp[0][1] = dp[1][0] = 0;//将第1个点旁的都设为0
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
scanf("%d",&dp[i][j]);
}
}
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
int maxn = -INF;
for(int k = 1;k < j;k++)
{
if(j%k==0)
{
if(maxn<dp[i][k])
maxn = dp[i][k];
}
}
if(i==1 && j==1) continue; //也能够用上边奇妙的初始化来代替特殊讨论边界
else if(i==1) dp[i][j] += max(dp[i][j⑴],maxn); //边界情况特殊讨论，由于本题可以有负数所以0其实不是最小的
else if(j==1) dp[i][j] += dp[i⑴][j];
else dp[i][j] += max(dp[i⑴][j],max(dp[i][j⑴],maxn));
//printf("de--%d ",dp[i][j]);
}
//printf("
");
}
printf("%d
",dp[n][m]);
}
return 0;
}
/*
1
3 8
⑴ ⑴ ⑴ ⑴ ⑴ ⑴ ⑴ ⑴
⑴ ⑴ ⑴ ⑴ ⑴ ⑴ ⑴ ⑴
⑴ ⑴ ⑴ ⑴ ⑴ ⑴ ⑴ ⑴
*/ //注意处理边界不然这组数据会出错<span style="color:#ff0000;">
</span>
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
