Home > Old Blog Posts > USACO 2.2.4 Subset Sums

USACO 2.2.4 Subset Sums


DP题。

设f[i][j]是用前i个自然数组成j的方法数,容易得出:

f[i][j]=f[i-1][j]+f[i-1][j-i]

另外空间复杂度可以利用滚动数组或指针来优化到O(n)

边界条件为f[1][1]=1

最后求的就是f[n][n*(n+1)/4]

显然若n*(n+1)/4不是整数,就可以直接输出0

代码:

/*
ID: dementr1
PROG: subset
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“subset.in”);
ofstream fout(“subset.out”);
int main()
{
int n,f[101][2550]={},i,j;
fin>>n;
if(n*(n+1)%4!=0) fout<<0<<endl;
else
{
f[1][1]=1;
for(i=2;i<=n;i++)
for(j=1;j<=n*(n+1)/4;j++)
{
f[i][j]=f[i-1][j];
if(j-i>=1)    f[i][j]+=f[i-1][j-i];
}
fout<<f[n][n*(n+1)/4]<<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: