code2198 数字三角形WWW

数字三角形的新变种

设要经过的点为x y，那么dp[x][k] = -Max    k=1~x and k!=y

其他一样：dp[i][j] = max(dp[i-1][j],dp[i-1[j-1])+a[i][j]

代码如下：

#include<iostream>
#define Size 55
using namespace std;

int n;
int x,y;
int a[Size][Size];
int dp[Size][Size];
int ans=-0x7f7f7f7f;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    cin>>x>>y;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(i==x && j!=y){
                dp[i][j]=-0x3f3f3f3f;
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
            }
            //cout<<dp[i][j]<<' '; 
        }
        //cout<<endl;
    }
    
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[n][i]);
    }
    cout<<ans<<endl;
    
    return 0;
}