Home > Old Blog Posts > USACO 3.1.6 Stamps

USACO 3.1.6 Stamps


设f[i]为组成i面值所需的最少面值数,方程类似于背包:f[i]=min{f[i-a[j]]+1} 1<=j<=n

初始条件:f[a[j]]=1 1<=j<=n

如果在计算过程中发现某个f[i]已经大于k则退出,答案即为i-1

如果输入数据的面值没有1 可以直接输出0退出

代码:

/*
ID: dementr1
PROG: stamps
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("stamps.in");
ofstream fout("stamps.out");
int k,n;
int a[300],f[2000001];
void init()
{
	fin>>k>>n;
	for(int i=1;i<=n;i++)
	{
		fin>>a[i];
		f[a[i]]=1;
	}
	if(!f[1])
	{
		fout<<0<<=i)
				if(!f[i]||(f[i-a[j]]&&f[i-a[j]]+1k) break;
	}
	fout<<
Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: