hdu 1028 Ignatius and the Princess III 简单dp
题目链接：hdu 1028 Ignatius and the Princess III
题意：对于给定的n，问有多少种组成方式
思路：dp[i][j]，i表示要求的数，j表示组成i的最大值，最后答案是dp[i][i]。那么dp[i][j]=dp[i][j-1]+dp[i-j][i-j]，dp[i][j-1]是累加1到j-1的结果，dp[i-j][i-j]表示的就是最大为j，然后i-j有多少种表达方式啦。因为i-j可能大于j，这与我们定义的j为最大值矛盾，所以要去掉大于j的那些值
/************************************************************** Problem:hdu 1028 User: youmi Language: C++ Result: Accepted Time:15MS Memory:1908K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep(i,from,to) for(int i=from;i<=to;i++) #define irep(i,to,from) for(int i=to;i>=from;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define eps 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl const double pi=4*atan(1.0); using namespace std; typedef long long ll; template <class T> inline void read(T &n) { char c; int flag = 1; for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0'; for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag; } int Pow(int base, ll n, int mo) { if (n == 0) return 1; if (n == 1) return base % mo; int tmp = Pow(base, n >> 1, mo); tmp = (ll)tmp * tmp % mo; if (n & 1) tmp = (ll)tmp * base % mo; return tmp; } //*************************** int n; const int maxn=200+10; ll dp[maxn][maxn]; void init() { zeros(dp); dp[0][0]=1; rep(i,1,120) { rep(j,1,i) { dp[i][j]=dp[i][j-1]+dp[i-j][i-j]; if(j<(i+1)/2) dp[i][j]-=dp[i-j][i-j]-dp[i-j][j]; } } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif init(); while(~sc(n)) { ptlld(dp[n][n]); } }