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 ;

}

相关文章