hdu 2571 dp入門題
來源：程序員人生 發(fā)布時間：2015-05-20 10:34:47 閱讀次數：2742次
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2571
常規(guī)dp，恰好讓我這菜鳥來找找 找狀態(tài)轉移方程的感覺。。
定義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覺得很受啟發(fā)，還可以將dp[][0] dp[0][] 都設為 -INF ，并且將dp[1][0] dp[0][1] 設為0 這樣邊界情況的時候就不會出現(xiàn)特殊的情況，不需要特殊討論了。
代碼+注釋：
#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>
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
