USACO 2.2 Subset 的状态转移方程
来源:学生作业帮 编辑:百度作业网作业帮 分类:综合作业 时间:2024/08/20 02:25:31
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
题意:把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 的状态转移方程](/uploads/image/z/20100199-31-9.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)
因为从大到小循环嘛,这样就不影响的啊,如果是从小到大,就会累加上去了,这个是比较高级的写法,等你以后写多了自然就理解了,我也不会推导.
再问: 高手留步 这歌一元数组的状态转移方程具体推导过程是怎样的? 比如从5到6的过程,能不能具体解释一下,谢谢
再答: dp[5][i] dp[6][j] 因为5推到6的话比如 dp[6][j]+=dp[5][j-i] 这里的j必然是大于i的,所以我们可以从大到小循环 然后小的推大的,这样是不影响结果的 你不理解因为你潜意识里面会觉得 他会影响到其他的,然后其他的又推回自己,这样是不对的,但是实际是,从大到小循环,然后由小推大,这样把大的推出来,并不影响其他的,因为循环是越来越小的,不可能再推回自己的,所以上面的方程是对的
再问: 不是认为影响 比如1-5组成10,和1-6组成10 1-6的里边分成两部分: 包含6的,1-5里就组成了4 不包含6的,1-5里就组成了10 问题是方程计算中中如何限制的5和6?
再答: 这个是这样的啊,当你循环到几的时候就去选几了啊,背包本来就是每一个只选择一次的。不用管两个是不是在一起啊。只要有一种情况的和是一半就行了。 不包含6的情况已经是在选择6之前已经选出来了
再问: 高手留步 这歌一元数组的状态转移方程具体推导过程是怎样的? 比如从5到6的过程,能不能具体解释一下,谢谢
再答: dp[5][i] dp[6][j] 因为5推到6的话比如 dp[6][j]+=dp[5][j-i] 这里的j必然是大于i的,所以我们可以从大到小循环 然后小的推大的,这样是不影响结果的 你不理解因为你潜意识里面会觉得 他会影响到其他的,然后其他的又推回自己,这样是不对的,但是实际是,从大到小循环,然后由小推大,这样把大的推出来,并不影响其他的,因为循环是越来越小的,不可能再推回自己的,所以上面的方程是对的
再问: 不是认为影响 比如1-5组成10,和1-6组成10 1-6的里边分成两部分: 包含6的,1-5里就组成了4 不包含6的,1-5里就组成了10 问题是方程计算中中如何限制的5和6?
再答: 这个是这样的啊,当你循环到几的时候就去选几了啊,背包本来就是每一个只选择一次的。不用管两个是不是在一起啊。只要有一种情况的和是一半就行了。 不包含6的情况已经是在选择6之前已经选出来了
请问,数学中subset和figurative numbers的中文翻译是什么?
usaco 里的Friday the Thirteenth请牛人帮忙
卡尔曼滤波理解问题看了几天的卡尔曼滤波一直有个地方不明白,网上的文献一般都有建立状态转移方程和量测方程,但是那只是对于仿
物质从一种状态转变成另一种状态,叫(),它在转化中伴随着()的转移
英语翻译是USACO中全题哦
usaco friday the thirteenth
线性定常连续系统状态转移矩阵的几种算法
关于USACO我做的dualpal测试点全过后.祝贺变成了USER: Nick A [sw20111]TASK: dua
高中化学转移电子问题高中常见转移一个电子的方程有哪些 比如氯气和氢氧化钠这些
usaco 1.1.3.Friday(黑色星期五)
NA2O2与H2O反应生成1.12L的O2(标准状态)..这一反应中转移的电子数是多少
如何判断一个矩阵是否为状态转移矩阵