背包dp – Tgotp-Blog

1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店

背包问题f[i]表示花费了i元所能凑出来的方案数。注意高精度…

c++代码如下:

 

NOIP2014t3P1941 飞扬的小鸟

第一次测 45 ,改了一个地方85。。。

然后满分是加一个完全背包优化。原本很简单,硬是被我一阵乱弄wa了一晚上,然后发现数组开爆了,蜜汁错误。

TAT

目前:NOIP2014 day1自测 100 + 70 + 45= 215

然而明明是可以 100 + 100 +85 =[……]

Read more

T7712 正整数分组

题目背景

成外培训:

Day 1 T 4

题目描述

将一堆正整数分为 2 组,要求 2 组的和相差最小。

例如:1 2 3 4 5,将 1 2 4 分为 1 组,3 5 分为 1 组,两组和相差 1,是所有方案中相 差最少的。

输入输出格式

输入格式:

第 1 行:一个数[……]

Read more

P1049 装箱问题

应xyf的要求写了纯c;

教学弟的blog。

思路:背包dp;

过程:f[i]表示背包使用i的容量时能装的最大价值,对于v向下处理,更新最大值,ok;

 

BZOJ 1004: [HNOI2008]Cards

姿势太弱,辣鸡取膜降我ac率;

裸的burnside
—-
置换:
1   2   3   4   5
a1 a2 a3 a4 a5
就是把1位置上的数换成a1上的数

置换群:一群置换就是置换群= =;;

循环:
1 2 3 4 5 6 7
7 5 2 4 6 3 1[……]

Read more

疯狂的火神

有优先条件的背包dp,就是说,对于背包 a,b,若a优先级大于b且 a,b最后都要选,就选先放a后放b。

题面

代码