TCO 2015 1C Hard - MagicWords
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13731&rd=16434
解き方
dpの問題。
dp[現在調べている桁数][beautifulcountの数][10の連続数]＝そのbeautifulcountの総数
とすると、前の結果について以下のようになる。
１：前の結果から１０が連続しないように１桁追加
→連続数が１になり、beautifulcountが１増える
２：前の結果から１０が連続するように１桁追加
→連続数が１増えて、beautifulcountが連続数＋１個増える
コード
class DevuAndBeautifulSubstrings {
public: long long countBeautifulSubstrings(int n, int cnt) {
int num=n*(n+1)/2;
long long dp[n+1][num][n+1];
memset(dp,0,sizeof(dp));
dp[1][1][1]=2;
for(int i=1;i<n;i++)for(int j=0;j<=num;j++)for(int prev=0;prev<=n;prev++){
if(dp[i][j][prev]!=0){
dp[i+1][j+1][1]+=dp[i][j][prev];
dp[i+1][j+1+prev][prev+1]+=dp[i][j][prev];
}
}
long long ret=0LL;
FORE(i,0,n+1)ret+=dp[n][cnt][i];
return ret;
}
};
public: long long countBeautifulSubstrings(int n, int cnt) {
int num=n*(n+1)/2;
long long dp[n+1][num][n+1];
memset(dp,0,sizeof(dp));
dp[1][1][1]=2;
for(int i=1;i<n;i++)for(int j=0;j<=num;j++)for(int prev=0;prev<=n;prev++){
if(dp[i][j][prev]!=0){
dp[i+1][j+1][1]+=dp[i][j][prev];
dp[i+1][j+1+prev][prev+1]+=dp[i][j][prev];
}
}
long long ret=0LL;
FORE(i,0,n+1)ret+=dp[n][cnt][i];
return ret;
}
};
