161
NYOJ171-聰明的kk
聰明的kk
時間限製：1000 ms | 內存限製：65535 KB
難度：3
描述
聰明的“KK”
非洲某國展館的設計靈感源於富有傳奇色彩的沙漠中陡然起伏的沙丘，體現出本國不斷變換和絢麗多彩的自然風光與城市風貌。展館由五部分組成，館內影院播放名為《一眨眼的瞬間》的寬銀幕短片，反映了建國以來人民生活水平和城市居住環境的驚人巨變。
可移動“沙丘”變戲法 的靈感源於其獨特而雄偉的自然景觀——富於傳奇色彩的險峻沙丘。宏偉的結構、可循環的建材，與大自然相得益彰。環繞一周，發現它正是從沙丘那不斷變換的形態中汲取靈感的。外形逼真到無論從哪個角度去觀察，都能清楚地辨識出沙丘的特征。
它“坡麵”高達20米，微風吹來，你是否感覺到沙的流動？用手去觸碰，卻發現原來是“魔術戲法”。它表麵的不鏽鋼麵板呈現出一種富於變幻的色彩，從不同角度觀察，呈現不同色澤，由此來模仿流動沙丘的光感。
走進第三展廳有一個超大的屏幕，通過奇妙的特效，讓觀眾猶如親身來到浩瀚的沙漠。更為奇妙的是，隻見一個小動物“KK”正從沙漠區域（矩形）的左上角沿著向右或向下的方向往右下角跑去。KK太聰明了，它居然能在跑的過程中會選擇吃掉盡可能多的蟲子線路。
你知道它吃掉多少蟲子嗎？
輸入
第一行：N M (1≤N M≤20 0≤Xij≤500(i=1,2?.N, j=1,2?,M)
)表示沙漠是一個N*M的矩形區域
接下來有N行：每行有M個正整數，Xi1 Xi2 ……Xim 表示各位置中的蟲子數（單個空格隔開）
假設“KK”隻能向右走或向下走。
輸出
輸出有一個整數， 表示“KK”吃掉最多的蟲子數。
樣例輸入
3 4
3 1 2 8
5 3 4 6
1 0 2 3
樣例輸出
24
來源
第三屆河南省程序設計大賽
//代碼1，深入搜索WA（就算對估計也是超時）
//看樣子需要動態規劃，於是改成代碼2
出錯代碼
代碼1：(WrongAnswer)
#include<stdio.h>
int a[50][50],n,m,flag;
void Fun(int x,int y,int sum)
{
int max1,max2;
if(flag==1)
return;
if(x==n-1&&y==m-1)
{
sum+=a[x][y];
printf("%d\n",sum);
flag=1;
return;
}
if(x+1<n)
{
max1=a[x+1][y];
if(y+1<m)
{
max2=a[x][y+1];
if(max1>=max2)
{
sum+=max1;
Fun(x+1,y,sum);
}
else
{
sum+=max2;
Fun(x,y+1,sum);
}
}
else
{
sum+=a[x+1][y];
Fun(x+1,y,sum);
}
}
else
{
sum+=a[x][y+1];
Fun(x,y+1,sum);
}
}
int main()
{
int i,j;
scanf("%d %d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&a[i][j]);
flag=0;
Fun(0,0,0);
return 0;
}
修改後
代碼2(AC代碼)：
#include<stdio.h>
#include<string.h>
int a[50][50];
int dp[50][50];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int i,j,n,m;
scanf("%d %d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&a[i][j]);
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
//記錄每一步情況的總值
if(i==0&&j==0)
dp[i][j]=a[i][j];
else
if(i==0)
{
dp[i][j]=dp[i][j-1]+a[i][j];
}
else
if(j==0)
{
dp[i][j]=dp[i-1][j]+a[i][j];
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
}
}
printf("%d\n",dp[n-1][m-1]);
return 0;
}
果然是赤裸裸的動態規劃！
最後更新：2017-04-03 12:56:03