HDU 1502 Regular Words

时间：2019-10-21 14:09:07 收藏：0 阅读：59

这题是动态规划，需要：打表，字符数组，动态规划。

状态表示：dp[i][j][k]表示的是有i个A，j个B和k个C满足要求的有多少种

转移方程：dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1]

边界：dp[0][0][0]=1;

因为会暴int，暴long long所以转换成字符数组来操作

#include<bits/stdc++.h>
using namespace std;
int n;
char dp[65][65][65][110];
void add(int i,int j,int k)
{
    for(int l=1;l<=100;l++)
    {
        if(i-1 >= j && j >= k &&i-1>=0&&dp[i-1][j][k][l]!=0)
            dp[i][j][k][l] += dp[i-1][j][k][l];
        if(i >= j-1 && j-1 >= k &&j-1>=0&&dp[i][j-1][k][l]!=0)
            dp[i][j][k][l] += dp[i][j-1][k][l];
        if(i >= j && j >= k-1 &&k-1>=0&&dp[i][j][k-1][l]!=0)
            dp[i][j][k][l] += dp[i][j][k-1][l];
    }
    for(int l=1;l<=100;l++)
    {
        int temp=dp[i][j][k][l]/10;
        dp[i][j][k][l+1]+=temp;
        dp[i][j][k][l]%=10;
    }
}
int main()
{
    dp[0][0][0][1]=1;
    for(int i=0;i<=60;i++)
        for(int j=0;j<=60;j++)
            for(int k=0;k<=60;k++)
                if(i>=j&&j>=k&&i+j+k)
                    add(i,j,k);
    while(~scanf("%d",&n))
    {
        int flag=0;
        for(int i=100;i>=1;i--)
        {
            if(dp[n][n][n][i]) flag=1;
            if(flag)
                printf("%c",dp[n][n][n][i]+‘0‘);
        }
        printf("\n\n");
    }
    return 0;
}

原文：https://www.cnblogs.com/Siv0106/p/11712763.html