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\n",a)
#define ptlld(a) printf("%I64d\n",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=*atan(1.0); using namespace std;
typedef long long ll;
template <class T> inline void read(T &n)
{
char c; int flag = ;
for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';
for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n * + c - ''; n *= flag;
}
int Pow(int base, ll n, int mo)
{
if (n == ) return ;
if (n == ) return base % mo;
int tmp = Pow(base, n >> , mo);
tmp = (ll)tmp * tmp % mo;
if (n & ) tmp = (ll)tmp * base % mo;
return tmp;
}
//*************************** int n;
const int maxn=+;
ll dp[maxn][maxn];
void init()
{
zeros(dp);
dp[][]=;
rep(i,,)
{
rep(j,,i)
{
dp[i][j]=dp[i][j-]+dp[i-j][i-j];
if(j<(i+)/)
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]);
}
}
上一篇:OpenCV基本架构[OpenCV 笔记0]


下一篇:opencv笔记3:trackbar简单使用