UVA 10912 Simple Minded Hashing

时间:2022-09-23 05:53:25

题意就略了。刚一看被数据吓住了。看到字符要求严格递增。那么如果字串长大于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.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == ? b : gcd(b, a % b);}
#define MAXN 360
#define MAXD 30
int l,s;
int tab[MAXD];
int dp[MAXD][MAXD][MAXN];
void init()
{
memset(dp,,sizeof(dp));
memset(tab,,sizeof(tab));
for (int i=; i<=; i++) tab[i] = tab[i-] + i;
for (int i=; i<=; i++) dp[][i][i] = ;
for (int i=; i<=; i++)
for (int j=i; j<=; j++)
for (int s=tab[i]; s<=; s++)
{
for (int k=; k<j && k<s; k++)
dp[i][j][s] += dp[i-][k][s-j];
}
}
int slove()
{
int ans = ;
for (int i=l; i<=; i++)
ans += dp[l][i][s];
return ans;
}
int main()
{
init();
int kase = ;
while (scanf("%d%d",&l,&s)!=EOF)
{
if (l == && s==) break;
if (l > || s > )
printf("Case %d: %d\n",kase++,);
else printf("Case %d: %d\n",kase++,slove());
}
return ;
}