首页 > 代码库 > UVA 10912 Simple Minded Hashing

UVA 10912 Simple Minded Hashing

2024-07-24 05:43:36   214人阅读

题意就略了。刚一看被数据吓住了。看到字符要求严格递增。那么如果字串长大于26那必然方案数目为0；同时1+2+3....+24+25+26=351如果大于这个数也是不可能的

令dp[i][j][k]表示第i位为第j个字符和为K时的方案数目

那么 dp[i][j][k]=sum(dp[i-1][m][k-t])  {m<j;k-t尝试将第j位置为t}

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 360#define MAXD 30int l,s;int tab[MAXD];int dp[MAXD][MAXD][MAXN];void init(){    memset(dp,0,sizeof(dp));    memset(tab,0,sizeof(tab));    for (int i=1; i<=26; i++) tab[i] = tab[i-1] + i;    for (int i=1; i<=26; i++) dp[1][i][i] = 1;    for (int i=2; i<=26; i++)        for (int j=i; j<=26; j++)            for (int s=tab[i]; s<=351; s++)    {        for (int k=1; k<j && k<s; k++)            dp[i][j][s] += dp[i-1][k][s-j];    }}int slove(){    int ans = 0;    for (int i=l; i<=26; i++)        ans += dp[l][i][s];    return ans;}int main(){    init();    int kase = 1;    while (scanf("%d%d",&l,&s)!=EOF)    {        if (l == 0 && s==0) break;        if (l > 26 || s > 351)        printf("Case %d: %d\n",kase++,0);        else printf("Case %d: %d\n",kase++,slove());    }    return 0;}

 

UVA 10912 Simple Minded Hashing


联系
我们