本文主要是介绍UVA - 10313 Pay the Price，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：在1-300之间，给你n，如果后面没跟着数字，代表用1-n的的种数凑成n，如果有一个数的话代表用1-l1种数凑成n,如果还有l2，代表用种数大于l1,小于l2的数凑成n,这貌似没思路啊，枚举的话好像不是太可能啊，后来看到这题涉及到一个结论ferrers图的性质：数n拆分成k个数的和的拆分数，和数n拆分成最大数为k的拆分数相等，然后就用
dp[i][j]代表用大小不超过j的数凑成i的方法个数，还是选与不选的考虑，如果选j的话，dp[i][j] = dp[i-j][j],不选的话
dp[i][j] = dp[i][j-1]，所以dp[i][j] = dp[i][j-1] + dp[i-j][j],当然如果i < j的话，那么就只能用j-1去凑，至于能不能凑又是之前的事啦
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 305;long long dp[MAXN][MAXN];
char str[1000];int main(){for (int i = 0; i <= 300; i++){dp[i][0] = i?0:1; //初始化for (int j = 1; j <= 300; j++)if (i >= j)dp[i][j] = dp[i-j][j] + dp[i][j-1];else dp[i][j] = dp[i][j-1];}while (gets(str)){int n,l1=-1,l2=-1;sscanf(str,"%d %d %d",&n,&l1,&l2);l1 = min(l1,300);l2 = min(l2,300);if (l1 == -1)printf("%lld\n",dp[n][n]);else if (l2 == -1)printf("%lld\n",dp[n][l1]);else {if (l1 == 0)printf("%lld\n",dp[n][l2]);else printf("%lld\n",dp[n][l2]-dp[n][l1-1]);}}return 0;
}这篇关于UVA - 10313 Pay the Price的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
