本题卡1s都行

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 3088ms

├ 测试数据 05：答案正确... 2978ms

├ 测试数据 06：答案正确... 3103ms

├ 测试数据 07：答案正确... 2869ms

├ 测试数据 08：答案正确... 2791ms

├ 测试数据 09：答案正确... 2994ms

├ 测试数据 10：答案正确... 3041ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：20864ms

超慢，ばがばがぃ。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 2291ms

├ 测试数据 05：答案正确... 2353ms

├ 测试数据 06：答案正确... 2291ms

├ 测试数据 07：答案正确... 2322ms

├ 测试数据 08：答案正确... 2338ms

├ 测试数据 09：答案正确... 2353ms

├ 测试数据 10：答案正确... 2306ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：16254ms

晕死巨慢，2000多MS

只要知道至多只有一对夫妇一起住就行了

我第100个A的，哈哈！

真的觉得很费解..

为什么不考虑夫妻才能AC..

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 1009ms

├ 测试数据 05：答案正确... 978ms

├ 测试数据 06：答案正确... 1119ms

├ 测试数据 07：答案正确... 1025ms

├ 测试数据 08：答案正确... 1056ms

├ 测试数据 09：答案正确... 1088ms

├ 测试数据 10：答案正确... 1025ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：7300ms

我觉得数据没错啊……

f[k,i,j]表示前i个房间住i个男性和j个女性的最小花费，g[k,i,j]表示相应方案中住一起的夫妇数

f[k,i,j]:=min(f[k-1,i-x[k],j]+y[k],f[k-1,i,j-x[k]]+y[k],f[k-1,i-1,j-1]+y[k](g[k-1,i-1,j-1]

做完这题感觉会被丘比特惩罚。。。

不准夫妻开包间的题……

同~~不管夫妻可以AC

管一对夫妻就WA完

我和ZHUDONGHE一样，AC了，但怀疑数据有错

虽然AC了,但是觉得这题数据有问题. 自己一个正确的程序没过,但错的程序却过了. ft...,请看在讨论区里我的话题.

为什么不出以下数据

1 1 1 1

1 4

不然夫妻根本不要考虑的阿

不知道是数据的问题还是题目设计的问题让一个有些想头的DP变成了knap

那位大侠讲讲，怎么做哦

夫妻要同住的话只要一对夫妻就可以了，因为2对夫妻的话只要2间房一个住2男 一个住2女就可以了^_^

居然是这样

但是只有一对夫妻怎么做呢

不管夫妻直接2维背包竟然AC了！，惊喜之余希望有人证明

dp

因为忘了一个判断，考试的时候0分，又浪费了我1个多小时555555555555555555

夫妻要同住的话只要一对夫妻就可以了，因为2对夫妻的话只要2间房一个住2男 一个住2女就可以了^_^

呃，题目数据太水，不考虑夫妻同房也能过
不过楼下说二维背包的请考虑这组数据：1 1 1 1 2 10 （ans：10） 这组数据只能1间夫妻同房
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

int n[305], p[305];
int g[305][305][2];

int main()
{
memset(g, 0x3f, sizeof(g));
int m, f, r, c; cin>>m>>f>>r>>c;
for(int i=1;i<=r;i++) scanf("%d%d", &n[i], &p[i]);
g[0][0][0]=0;
for(int i=1;i<=r;i++)
for(int j=m;j>=0;j--)
for(int k=f;k>=0;k--)
for(int l=min(min(j, k), min(1, c));l>=0;l--){
if(n[i]>=2&&l>0) g[j][k][l]=min(g[j][k][l], g[j-1][k-1][l-1]+p[i]);
int x=min(n[i], j), y=l;
if(j-x<l) y=j-x;
g[j][k][l]=min(g[j][k][l], g[j-x][k][y]+p[i]);
x=min(n[i], k);
y=l;
if(k-x<l) y=k-x;
g[j][k][l]=min(g[j][k][l], g[j][k-x][y]+p[i]);
}
if(c>0){
if(g[m][f][0]==0x3f3f3f3f&&g[m][f][1]==0x3f3f3f3f) cout<<"Impossible"<<endl;
else cout<<min(g[m][f][1], g[m][f][0])<<endl;
}
else{
if(g[m][f][0]==0x3f3f3f3f) cout<<"Impossible"<<endl;
else cout<<g[m][f][0]<<endl;
}
return 0;
}

事实证明，是没有impossible的。。