动态规划——棋盘

数字三角形

经典例题，有记忆化搜索，正推，逆推三种方法

如果记录路径，可以开一个数组记录状态是由哪个子状态推出来的

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn = 200;
int n,dp[maxn][maxn],value[maxn][maxn];

int main(){
    cin>>n;
    for(int i = 1;i <=n;i++){
        for(int j = 1;j <= i;j++){
            cin>>value[i][j];
        }
    }
    memset(dp,-1,sizeof(dp));
    for(int i = 1;i <= n;i++) dp[n][i] = value[n][i];
    for(int i = n - 1;i >= 1;i--){
        for(int j = 1;j <= i;j++){
            dp[i][j] = value[i][j] + max(dp[i+1][j],dp[i+1][j+1]);
        }
    } 
    cout<<dp[1][1];
    return 0;
}

数字三角形w

同数字三角形，要求数字总和取模100后最大，既然总和大的余数不一定大，所以转化为可行性判断

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,dp[50][50][105],map[50][50],ans = 0;
int x,y;
int main(){
    cin>>n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            scanf("%d",&map[i][j]);
        }
    }
    dp[1][1][map[1][1]%100] = 1;
    for(int i = 2;i <= n;i++){
        for(int j = 1;j <= i;j++){
            for(int k = 0;k <= 99;k++){
                if(dp[i-1][j-1][k] || dp[i-1][j][k]){
                    dp[i][j][(k+map[i][j])%100] = 1;
                    if(i == n) ans = max(ans,(k+map[i][j])%100);    
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

数字三角形ww

同数字三角形，要求必须经过x div 2,y div 2这个点

有一个技巧，把这个点的值加上一个特别大的数，就一定会经过这个点

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,dp[50][50],map[50][50],ans = 0,hehe = 100000000;
int main(){
    cin>>n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            scanf("%d",&map[i][j]);
        }
    }
    map[n/2][n/2] += hehe;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + map[i][j];
            ans = max(dp[i][j],ans);
        }
    }
    cout<<ans-hehe;
    return 0;
}

数字三角形www

同上个题，只不过必过点任意

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,dp[50][50],map[50][50],ans = 0,hehe = 100000000;
int x,y;
int main(){
    cin>>n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            scanf("%d",&map[i][j]);
        }
    }
    cin>>x>>y;
    map[x][y] += hehe;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + map[i][j];
            ans = max(dp[i][j],ans);
        }
    }
    cout<<ans-hehe;
    return 0;
}

最低通行费用

从左上角到右下角，往右或往下走，使沿途的权值和最小

一定要注意边界的问题

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int map[105][105],dp[105][105],n;
    cin>>n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            cin>>map[i][j];
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(i > 1 && j > 1)dp[i][j] = map[i][j] + min(dp[i-1][j],dp[i][j-1]);
            else if(i > 1 && j == 1) dp[i][j] = map[i][j] + dp[i-1][j];
            else if(j > 1 && i == 1) dp[i][j] = map[i][j] + dp[i][j-1];
            else dp[i][j] = map[i][j];
        }
    }
    cout<<dp[n][n];
    return 0;
}

Wikioi 2152 滑雪

题目描述 Description

trs喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。
例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。

输入描述 Input Description

输入文件

第1行: 两个数字r，c(1<=r,c<=100)，表示矩阵的行列。
第2..r+1行:每行c个数，表示这个矩阵。

输出描述 Output Description

输出文件

仅一行: 输出1个整数，表示可以滑行的最大长度。

样例输入 Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出 Sample Output

数据范围及提示 Data Size & Hint

思路：

枚举起点+记忆化搜索

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define mx 150
 7 #define maxint 10000000
 8 using namespace std;
 9 int r,c,a[mx][mx],vis[mx][mx],bx,by,mn,dp[mx][mx],ans;
10 void input(){
11     cin>>r>>c;
12     mn = 0;
13     memset(a,maxint,sizeof(a));
14     for(int i = 1;i <= r;i++){
15         for(int j = 1;j <= c;j++){
16             cin>>a[i][j];
17             if(a[i][j] > mn){
18                 mn = a[i][j];
19                 by = i;
20                 bx = j;
21             }
22         }
23     }
24     
25 }
26 int dfs(int y,int x){
27     if(vis[y][x]) return dp[y][x];
28     vis[y][x] = 1;
29     if(y - 1 > 0 && a[y][x] > a[y-1][x])dp[y][x] = max(dp[y][x],dfs(y-1,x));
30     if(y + 1 <= r && a[y][x] > a[y+1][x])dp[y][x] = max(dp[y][x],dfs(y+1,x));
31     if(x - 1 > 0 && a[y][x] > a[y][x-1])dp[y][x] = max(dp[y][x],dfs(y,x-1));
32     if(x + 1 <= c && a[y][x] > a[y][x+1])dp[y][x] = max(dp[y][x],dfs(y,x+1));
33     return ++dp[y][x];
34 }
35 void work(){
36     ans = 0;
37 
38     for(int i = 1;i <= r;i++){
39         for(int j = 1;j <= c;j++){    
40             dfs(i,j);
41         }
42     }
43     for(int i = 1;i <= r;i++){
44         for(int j = 1;j <= c;j++){    
45             ans = max(ans,dp[i][j]);
46         }
47     }
48     cout<<ans<<endl;
49 }
50 int main(){
51     input();
52     work();
53     return 0;
54 }

View Code

难题：

传纸条（多线程dp，最优性方法解决判定问题）No.3