HDU1284 환전 문제, 가방 문제

1163 단어
가장 고전적인 가방 문제
/*******************************************************************************
 # Author : Neo Fung
 # Email : [email protected]
 # Last modified: 2012-06-13 16:07
 # Filename: acm.cpp
 # Description : 
 ******************************************************************************/
#ifdef _MSC_VER
#define DEBUG
#define _CRT_SECURE_NO_DEPRECATE
#endif

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
using namespace std;

const int kMAX=33000;
const double kEPS=10E-6;

long long dp[kMAX];

int main(void)
{
#ifdef DEBUG  
  freopen("../stdin.txt","r",stdin);
  freopen("../stdout.txt","w",stdout); 
#endif  

  int n;
	memset(dp,0,sizeof(dp));
	dp[0]=1ll;

	for(int i=1;i<=3;++i)
		for(int j=i;j<kMAX;++j)
			dp[j]+=dp[j-i];

  while(~scanf("%d",&n) && n)
  {
		printf("%lld
",dp[n]); } return 0; }

좋은 웹페이지 즐겨찾기