[CODEVS] 2189 数字三角形W

数字三角形

要求走到最后mod 100最大

可达性DP（好像是这样叫）

用bool数组f[i][j][k]表示位置(i,j)能否得到k（mod 100意义下）

转移条件 f[i][j][k]=f[i+1][j][[k-a[i][j]+100)%100] | f[i+1][j+1][[k-a[i][j]+100)%100]

//Writer:GhostCai && His Yellow Duck

#include<iostream>

using namespace std;

const int MAXN=26;

int n;

int a[MAXN][MAXN];

bool f[MAXN][MAXN][100];

int main(){

    cin>>n;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=i;j++){

            cin>>a[i][j];

        }

    }

    for(int i=1;i<=n;i++) f[n][i][((a[n][i]%100)+100)%100]=1;

    for(int i=n-1;i>=1;i--){

        for(int j=1;j<=i;j++){

            for(int k=0;k<=99;k++){

                int v=(((k-a[i][j])%100)+100)%100 ;

                f[i][j][k]=f[i+1][j][v] | f[i+1][j+1][v];

            }

        }

    }

    for(int i=99;i>=0;i--){

        if(f[1][1][i]){

             cout<<i<<endl;

             return 0;

        }

    }

}

巴特西

[CODEVS] 2189 数字三角形W

最新文章

热门文章