USACO 2.2 Subset 的状态转移方程题意:把1~n这n个数分成两个堆,使它们的和相等问:一共有多少种分法?我们其实可以把它变成另一个问题:把1~n个数,组成n*(n+1)/2的一半有多少种方法?(用一些数
来源:学生作业帮助网 编辑:六六作业网 时间:2025/02/07 14:15:11
USACO 2.2 Subset 的状态转移方程题意:把1~n这n个数分成两个堆,使它们的和相等问:一共有多少种分法?我们其实可以把它变成另一个问题:把1~n个数,组成n*(n+1)/2的一半有多少种方法?(用一些数
USACO 2.2 Subset 的状态转移方程
题意:把1~n这n个数分成两个堆,使它们的和相等
问:一共有多少种分法?
我们其实可以把它变成另一个问题:把1~n个数,组成n*(n+1)/2的一半有多少种方法?(用一些数组成一个数有多少方法?)
到这里成了用一组数组成一个数有多少方法 ,
二元数组表示:
data[i][j]表示前i个数字构成j的方案数
这样的话可以得到状态转移方程
data[i][j]=data[i-1][j-i]+data[i-1][j]
这个好理解
百度百科里代码:
#include
using namespace std;
const unsigned int MAX_SUM = 1024;
int n;
unsigned long long int dyn[MAX_SUM];
ifstream fin ("subset.in");
ofstream fout ("subset.out");
int main()
{
fin >> n;
fin.close();
int s = n*(n+1);
if (s % 4)
{
fout
USACO 2.2 Subset 的状态转移方程题意:把1~n这n个数分成两个堆,使它们的和相等问:一共有多少种分法?我们其实可以把它变成另一个问题:把1~n个数,组成n*(n+1)/2的一半有多少种方法?(用一些数
因为从大到小循环嘛,这样就不影响的啊,如果是从小到大,就会累加上去了,这个是比较高级的写法,等你以后写多了自然就理解了,我也不会推导.