點擊打開鏈接NYOJ 171
1題目：
聰明的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
2思路：DP（最大的路徑和）
3分析：假設當前的位置在G[i][j],那麼根據kk只能往右和往下，那麼我們知道G[i][j]的上一步來自G[i-1][j]和G[i][j-1],那麼我們假設dp[i][j]為到達G[i][j]的最大值，那麼有dp[i][j] = max(dp[i-1][j] , dp[i][j-1])+G[i][j];所以只要去對每一個位置進行推到，那麼最後的ans就是dp[n][m]（這裡為了計算方便，把下標從1開始）
4代碼：
[cpp]
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAXN 30
#define INF -0xFFFFFFF
int n , m;
int G[MAXN][MAXN];
int dp[MAXN][MAXN];
int max(int a , int b){
return a>b?a:b;
}
void solve() {
int i , j;
memset(dp , 0 , sizeof(dp));
for(i = 1 ; i <= n ; i++){
for(j = 1 ; j <= m ; j++)
dp[i][j] = max(dp[i-1][j] , dp[i][j-1])+G[i][j];
}
printf("%d\n" , dp[n][m]);
}
int main() {
//freopen("input.txt", "r", stdin);
while(scanf("%d%d%*c" , &n , &m) != EOF){
for(int i = 0 ; i <= n ; i++) G[i][0] = INF;
for(int i = 0 ; i <= m ; i++) G[0][i] = INF;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= m ; j++)
scanf("%d" , &G[i][j]);
}
solve();
}
return 0;
}
