1709: 搬行李

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 15  Solved: 2
[Submit][Status][Web Board]

Description

开学了，又要搬行李，这次你粑粑有2辆车帮你搬，但是不能超载哦。现在给出n(n<=10)件行李的体积，以及2个车子的容量c1,c2(c1<=100,c2<=100)，问题就是需要搬运几次？(当然，2辆车是同时过去的，同时回来的，这样算一次)

Input

输入一行T

第二行 n,c1,c2

第三行 n个数

Output

输出需要运输的次数（每组案例输出后面有一行空行）

Sample Input

2

6 12 13

3 9 13 3 10 11

7 1 100

1 2 33 50 50 67 98

Sample Output

zcmu #1: 2

 

zcmu #2: 3

 

【分析】

数据很小 n<=10 ，但是显然上来搜就会gg...那当然按照吉老师的说法应该还是有一些优秀的黄金搜索能搜过去的吧...

如果不考虑搜索，那么这么小的n就是摆明了告诉你状压dp的...（1<<n）压一下选择物品的物品，如果从这里考虑的话就会稍微清晰一点了......那么对于两种状态，只要这两种状态之间没有重复的选择，也就是如果有两个状态x,y ,那么只要x&y == 0 就意味着这两种选择的状态是不冲突的，就可以合并，接下去只要找出最小的合并步数合并成(1<<n)-1就可以求出答案了

仿佛解决了一切问题的思路。。。。

虽然状态合并解决了，但是什么样的状态才能合并呢？ 显然这里还有一个问题，不是任意两个状态只要x&y==0就可以合并的，显然我们应该考虑的是从当前状态x出发，经过一趟运输状态y，合并出目标状态x|y,同时步数+1，所以我们还需要解决运输状态，运输状态很好理解，只要一趟运输可以装的下，那就是一个可行的运输状态

这样考虑的话就比较明朗了，对所有的状态我们只要考虑每个运输状态往前装就行了....就变成类似背包的思路了...

所以首先解决运输状态的pending，对一个状态，怎么判断这是一个可行的运输状态，显然就是这次状态中被选择的物品可以装上两辆车，那么我们对一辆车进行背包，剩下的物品全塞进另一辆车就行了...

这里假装自己加了个优化，用体积小的车做背包......当然并没有什么必要...数据范围太小了

然后对所有可行的运输状态做一次背包...直接塞就行了...gg

太久没做题了....状压dp真的写不来了...太菜了

【代码】

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int f[10000];
int a[10000];
int v[10000];
int bag[10000];
int len,n,c1,c2;bool check(int x){len = 0;int all = 0;for (int i = 0 ; i < n ; ++i)if (x & (1<<i)){v[len++] = a[i];all += a[i];}memset(bag,0,sizeof(bag[0]) * (c1 + 10));for (int i = 0 ; i < len ; ++i)for (int j = c1 ; j >= v[i] ; --j)bag[j] = max(bag[j],bag[j - v[i]] + v[i]);all -= bag[c1];if (all <= c2) return true;return false;
}int main()
{int pp;scanf("%d",&pp);for (int cas = 1 ; cas <= pp; ++cas){scanf("%d%d%d",&n,&c1,&c2);if (c1 > c2) swap(c1,c2);for (int i = 0 ; i < n ; ++i) scanf("%d",&a[i]);memset(f,0x3f3f3f3f,sizeof(f[0]) * ( (1<<n) + 100) );vector<int> can;	for (int i = 0 ; i < (1<<n) ; ++i){if (check(i)){f[i] = 1;can.push_back(i);}}len = can.size();for (int i = 0 ; i < len ; ++i){for (int j = (1<<n) - 1 ; j >= 0 ; --j){if ( (can[i] & j) == 0){int go = can[i] | j;f[go] = min(f[j] + 1,f[go]);}}}printf("zcmu #%d:\n%d\n\n",cas,f[(1<<n) - 1]);}return 0;
}