Home > Old Blog Posts > USACO 2.3.4 Money Systems

USACO 2.3.4 Money Systems


DP。

令f[i][j]表示前i种面额组合出j面值的方法数,很容易得到方程f[i][j]=f[i-1][j]+f[i-1][j-a[i]]+f[i-1][j-2*a[i]]+…+f[i-1][j- k*a[i]],k=j/a[i],。进一步分析后改进方程为f[i] [j]=f[i-1][j]+f[i][j-a[i]],复杂度为O(n^2)。 空间复杂度可以进行进一步的优化。

代码:

/*
ID: dementr1
PROG: money
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“money.in”);
ofstream fout(“money.out”);
int main()
{
long long V,N,i,j,f[25][10001]={},a[25]={};
fin>>V>>N;
for(i=0;i<V;i++) fin>>a[i];
for(i=0;i<=N;i+=a[0]) f[0][i]=1;
for(i=1;i<V;i++)
{
for(j=0;j<a[i]&&j<=N;j++)
{
f[i][j]=f[i-1][j];
}
for(j=a[i];j<=N;j++)
{
f[i][j]=f[i-1][j]+f[i][j-a[i]];
}
}
fout<<f[V-1][N]<<endl;
return 0;
}

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: