체크dp

1256 단어
dp[i][j][k]기록이 i, j 노드에 도착했을 때 이들의 차이는 x의 방안수이다
매번 매거x(tmp+=(a[i][j])%=11(tmp2=(11-tmp1)%=11)%=11 여기 있는 tmp2는 사람과 검 사이의 전환을 실현한다
#include<cstdio>
#include<cstring>
using namespace std;
const int N=480,M=11,mod=1e9+7;
char s[N];
int a[N][N],n,m,ans,dp[N][N][M],T,kase=0;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            for(int j=0;j<m;j++)
                a[i][j]=s[j]-'0';
        }
        for(int i=n-1;i>=0;i--)
        {
            for(int j=m-1;j>=0;j--)
            {
                for(int x=0;x<11;x++)
                {
                    int tmp=(x+a[i][j])%11;
                    int tmp2=(11-tmp)%11;
                    if(i<n-1) (dp[i][j][x]+=dp[i+1][j][tmp2])%=mod;
                    if(j<m-1) (dp[i][j][x]+=dp[i][j+1][tmp2])%=mod;
                    if(tmp==0)(dp[i][j][x]+=1)%=mod;
                    if(x==0) (ans+=dp[i][j][x])%=mod;
                }
            }
        }
        printf("Case %d: %d
",++kase,ans); } return 0; }

좋은 웹페이지 즐겨찾기