1824. 数塔III

10175102262 LarsPendragon

变相的数塔,我的想法是把每一个数字在每一条路径中可能出现的个位数存起来再动态规划。附C代码:

#include <stdio.h>
int main(void)
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        int n, num[101][101], i, j, k, y, m=0;
        char x[101][101][10];//存储可能出现的个位数字
        scanf("%d",&n);
        for(i=1; i<=n; i++) for(j=1; j<=i; j++) {scanf("%d",&num[i][j]); for(k=0; k<10; k++) x[i][j][k]='0';/*初始化*/}
        x[1][1][num[1][1]%10]='1';
        for(i=2; i<=n; i++)
        {
            for(j=1; j<=i; j++)
            {
                if(j!=1)
                    for(k=0; k<10; k++)
                        if(x[i-1][j-1][k]-'0')
                            x[i][j][(num[i][j]+k)%10]='1';
                if(j!=i)
                    for(k=0; k<10; k++)
                        if(x[i-1][j][k]-'0')
                            x[i][j][(num[i][j]+k)%10]='1';
            }
        }
        for(j=1; j<=n; j++)
            for(k=0; k<10; k++)
                if(x[n][j][k]-'0')
                    if(m<k) m=k;
        printf("%d\n",m);
    }
}
你当前正在回复 博客/题目
存在问题!