USACO section2.2 Subset Sums問題解&コード
うん...3回も交際したことがある...またUSACOのデータに人間として教えられた...
まずこの問題は簡単な01リュックサックです...あるいはプッシュ...
O(n^3)だけでいいのですが…
そして...ll大法好...
最後に...なぜ私は中間数が整数ではないかもしれないという事実を忘れたのか...私も知らない...
まずこの問題は簡単な01リュックサックです...あるいはプッシュ...
O(n^3)だけでいいのですが…
そして...ll大法好...
最後に...なぜ私は中間数が整数ではないかもしれないという事実を忘れたのか...私も知らない...
/*
ID:rainbow16
LANG:C++
TASK:subset
*/
#include<iostream>
#include<stdio.h>
using namespace std;
int n,MAX;
long long dp[800];
int main(void)
{
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
cin>>n;
MAX=(1+n)*n/2;
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=MAX;j>=i;j--)
dp[j]+=dp[j-i];
if(MAX%2==0)
cout<<dp[MAX/2]/2<<endl;
else
cout<<'0'<<endl;
return 0;
}