Ingenuous Cubrency

又是dp问题，我又想了2 30分钟，一点思路也没有，最后又是看的题解，哎，为什么我做dp的题这么烂啊！

【题目类型】dp

&题意：

21种硬币，第i种的价值是i* i* i，给出一个数额，问有几种方法能组成这个数额。

比如这个数额是21，那么输出3，有3种方法：

1:21个1

2:1个8,13个1

3:2个8,5个1

&题解：

每次dp，要先想到dp的对象，这次就是要枚举输入的n。

dp数组也要想到边界，这次的边界就是dp[0]=1;

外层要枚举21种数，内层枚举n。注意顺序，21种数是从1开始到21的，因为前面的总是比后面小，这样就能为后面的服务，不会缺少情况了。内层是从coin[i]到n，因为你要注意dp方程的顺序，它用到了前面的值，所以要正着枚举。

【时间复杂度】O(n)

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))

#define rep(i,b) for(int i=0;i<(b);i++)

#define rez(i,a,b) for(int i=(a);i<=(b);i++)

#define red(i,a,b) for(int i=(a);i>=(b);i--)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

#define PU(x) puts(#x);

#define PI(A) cout<<(A)<<endl;

#define DG(x) cout<<#x<<"="<<(x)<<endl;

#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;

#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS = 1e-9 ;

/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */

const int MAXN = 10000 + 5 ;

int coin[50],n;

ll dp[MAXN];

void Solve()

{

    while(~SI(n)){

    	cle(dp,0);

    	dp[0]=1;

    	for(int i=1;i<=21;i++){

    		for(int j=coin[i];j<=n;j++){

    			dp[j]+=dp[j-coin[i]];

    		}

    	}

    	PI(dp[n])

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("1.in", "r", stdin);

    freopen("1.out","w",stdout);

#endif

//iostream::sync_with_stdio(false);

//cin.tie(0), cout.tie(0);

	// int T;cin>>T;while(T--)

	rez(i,1,21) coin[i]=i*i*i;

    Solve();

    return 0;

}

巴特西

UVA 11137 Ingenuous Cubrency（dp）

Ingenuous Cubrency

最新文章

热门文章