首页 > 代码库 > SPOJ ANARC05H 计数DP

SPOJ ANARC05H 计数DP

2024-07-16 18:50:29   220人阅读

给定一个数字串，问有多少种拆分方法，题目所谓的拆分，就是分成若干个子块，每个块的和 即为各个数字相加，当前块的和一定要小于等于后面的块的和

比如1117  就有这些[1-117], [1-1-17], [1-11-7], [1-1-1-7], [11-17],and [111-7]

肯定是计数DP，而且二维即可，不过第二维应该怎么设置是亮点，我也想了好多种方案，不过都被否定了，后来还是一种其实比较经典的方案进来了，就是代表当前最后一个块的和是多少，则当前dp[i][j] 由dp[i-1][k]转移过来，只要满足 j>=k即可呀

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;char str[30];int num[30];int suffix[30];int dp[30][250];int main(){    int kase=1;    while (scanf("%s",str)!=EOF)    {        if (str[0]==‘b‘){            break;        }        int len=strlen(str);        for (int i=0;i<len;i++){            num[i+1]=str[i]-‘0‘;            suffix[i+1]=suffix[i]+num[i+1];        }        memset(dp,0,sizeof dp);        for(int i=1;i<=len;i++){            for (int j=i;j>0;j--){                int tmp=suffix[i]-suffix[j-1];                if (j==1) dp[i][tmp]+=1;                else                for (int k=0;k<=tmp;k++)                dp[i][tmp]+=dp[j-1][k];            }        }        int ans=0;        for (int i=0;i<250;i++){           // if (dp[len][i]) cout<<i<<endl;            ans+=dp[len][i];        }        printf("%d. %d\n",kase++,ans);    }    return 0;}

　　


联系
我们