数字三角形模型

摘花生思路

• 最低通行费
  注意此题的边界处理

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=110,inf=0x3f3f3f3f;
int n;
int w[N][N],dp[N][N];

int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                scanf("%d",&w[i][j]);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(i==1&&j==1) dp[i][j]=w[i][j];
                else{
                    dp[i][j]=inf;
                    //边界处理
                    if(i>1) dp[i][j]=min(dp[i][j],dp[i-1][j]+w[i][j]);
                    if(j>1) dp[i][j]=min(dp[i][j],dp[i][j-1]+w[i][j]);
                    //dp[i][j]可能已经更新 
                    //所以不能与dp[i][j-1]取min 而要与dp[i][j-1]+w[i][j]取min
                }
        printf("%d",dp[n][n]);
    return 0;
}

• 方格取数
  
  贪心反例
  
  即每次最大都是当前情况下的最大并不一定保证最后的和最大
  既然无法先后走那么考虑同时走
  类比摘花生 可以做出四维DP
  即f[i1][j1][i2][j2]表示从(1,1)同时走到(i1,j1)和(i2,j2)的所有路线中的最大和
  再压缩为三维 最终转移有四种

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=11;
int n;
int w[N][N],f[N*2+1][N][N];

int main(){
    scanf("%d",&n);
    int a,b,c;
    while(cin>>a>>b>>c&&a&&b&&c) w[a][b]=c;
    for(int k=2;k<=2*n;++k)
        //i1,i2虽然从1->n 但是j1,j2判断越界 
        for(int i1=1;i1<=n;++i1)
            for(int i2=1;i2<=n;++i2){
                int j1=k-i1,j2=k-i2;
                if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
                    int t=w[i1][j1];
                    if(i1!=i2) t+=w[i2][j2];
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2-1]+t);
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2]+t);
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2-1]+t);
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2]+t);
                }
            }
    printf("%d",f[2*n][n][n]);
    return 0;
} 

网络