USACO 2.2 Subset 的状态转移方程题意:把1~n这n个数分成两个堆,使它们的和相等问:一共有多少种分法?我们其实可以把它变成另一个问题:把1~n个数,组成n*(n+1)/2的一半有多少种方法?(用一些数
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/31 00:36:03
![USACO 2.2 Subset 的状态转移方程题意:把1~n这n个数分成两个堆,使它们的和相等问:一共有多少种分法?我们其实可以把它变成另一个问题:把1~n个数,组成n*(n+1)/2的一半有多少种方法?(用一些数](/uploads/image/z/13292588-20-8.jpg?t=USACO+2.2+Subset+%E7%9A%84%E7%8A%B6%E6%80%81%E8%BD%AC%E7%A7%BB%E6%96%B9%E7%A8%8B%E9%A2%98%E6%84%8F%EF%BC%9A%E6%8A%8A1%7En%E8%BF%99n%E4%B8%AA%E6%95%B0%E5%88%86%E6%88%90%E4%B8%A4%E4%B8%AA%E5%A0%86%2C%E4%BD%BF%E5%AE%83%E4%BB%AC%E7%9A%84%E5%92%8C%E7%9B%B8%E7%AD%89%E9%97%AE%EF%BC%9A%E4%B8%80%E5%85%B1%E6%9C%89%E5%A4%9A%E5%B0%91%E7%A7%8D%E5%88%86%E6%B3%95%3F%E6%88%91%E4%BB%AC%E5%85%B6%E5%AE%9E%E5%8F%AF%E4%BB%A5%E6%8A%8A%E5%AE%83%E5%8F%98%E6%88%90%E5%8F%A6%E4%B8%80%E4%B8%AA%E9%97%AE%E9%A2%98%EF%BC%9A%E6%8A%8A1%7En%E4%B8%AA%E6%95%B0%2C%E7%BB%84%E6%88%90n%2A%28n%2B1%29%2F2%E7%9A%84%E4%B8%80%E5%8D%8A%E6%9C%89%E5%A4%9A%E5%B0%91%E7%A7%8D%E6%96%B9%E6%B3%95%3F%EF%BC%88%E7%94%A8%E4%B8%80%E4%BA%9B%E6%95%B0)
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的一半有多少种方法?(用一些数
因为从大到小循环嘛,这样就不影响的啊,如果是从小到大,就会累加上去了,这个是比较高级的写法,等你以后写多了自然就理解了,我也不会推导.