因为它的状态比较多，比较吓人。（但是这题有错误，夫妻条件不管才能过。）

说说正解吧。

dp[i][j][h][k]表示前i个房间，住了j对夫妻，一共住了h个男的，k个女的这个状态的最小费用。

然后就是暴力枚举每一个房间，更新数组了。

这里有一个很有趣的地方就是，夫妻房最多用1对就已经最优了，因为你用两对的话，可以把他们拆散，2个男的一件，2个女的一件。

所以这里如果考虑夫妻的，是可以卡到你超时的，如果注意到夫妻 只能用一对，那就不会超时。

背包动规

#include<iostream>
#include<cstring>
using namespace std;
int b[301],p[301];
int dp[601][601][2];
int main()
{
    int m,f,r,c;
    cin>>m>>f>>r>>c;
    memset(dp,127,sizeof(dp));
    for(int i=1;i<=r;i++)
       cin>>b[i]>>p[i];
    dp[0][0][0]=0;
    for(int l=1;l<=r;l++)
           for(int i=m;i>=0;i--) 
               for(int j=f;j>=0;j--)
               {
                   if(b[l]>=2)dp[i][j][1]=min(dp[i][j][0]+p[l],dp[i][j][1]);
                   for(int o=1;o<=b[l];o++)
                   {
                       if(i+o<=m+c&&i-o>=0)
                       dp[i][j][0]=min(dp[i][j][0],dp[i-o][j][0]+p[l]);
                       if(j+o<=f+c&&j-o>=0)
                       dp[i][j][0]=min(dp[i][j][0],dp[i][j-o][0]+p[l]);
                   }
               }
    int ans=9999999;
        ans=min(dp[m-1][f-1][1],dp[m][f][0]);
    if(ans!=9999999)cout<<ans;
    else cout<<"Impossible";
    return 0;
}

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int dp[300 + 2][300 + 2][300 + 2];
const int maxn = 300 + 20;
int a[maxn];
int cost[maxn];
void work() {
int nan, nv, room, toget;
cin >> nan >> nv >> room >> toget;
for (int i = 1; i <= room; ++i) {
cin >> a[i] >> cost[i];
}
memset(dp, 0x3f, sizeof dp);
dp[0][0][0] = 0;
toget = min(toget, 1);
toget = 0;
for (int i = 1; i <= room; ++i) {
for (int j = toget; j >= 0; --j) {
for (int h = nan; h >= 0; --h) {
for (int k = nv; k >= 0; --k) {
if (k >= a[i]) {
dp[j][h][k] = min(dp[j][h][k], dp[j][h][k - a[i]] + cost[i]);
} else {
dp[j][h][k] = min(dp[j][h][k], dp[j][h][0] + cost[i]);
}
if (h >= a[i]) {
dp[j][h][k] = min(dp[j][h][k], dp[j][h - a[i]][k] + cost[i]);
} else {
dp[j][h][k] = min(dp[j][h][k], dp[j][0][k] + cost[i]);
}
if (j >= 1 && h >= 1 && k >= 1) {
dp[j][h][k] = min(dp[j][h][k], dp[j - 1][h - 1][k - 1] + cost[i]);
}
// dp[0][h][k] = min()
}
}
}
}
// cout << dp[0][2][1] << endl;
int ans = inf;
for (int i = 0; i <= toget; ++i) {
ans = min(ans, dp[i][nan][nv]);
}
if (ans == inf) {
cout << "Impossible" << endl;
return;
}
cout << ans << endl;
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return 0;
}

大家都写的这种版本
#include<bits/stdc++.h>
using namespace std;
#define xyf main
int m,f,r,c;
int b[301],p[301];
int dp[301][301][2];
int xyf()
{
cin>>m>>f>>r>>c;
memset(dp,0x3f3f3f,sizeof(dp));
for(int i=1;i<=r;++i)
cin>>b[i]>>p[i];
dp[0][0][0]=0;
for(int l=1;l<=r;++l)
for(int i=m;i>=0;--i)
for(int j=f;j>=0;--j)
{
if(b[l]>=2)
dp[i][j][1]=min(dp[i][j][0]+p[l],dp[i][j][1]);
for(int o=1;o<=b[l];++o)
{
if(o+i<=m+c&&o<=i)
dp[i][j][0]=min(dp[i][j][0],dp[i-o][j][0]+p[l]);
if(o+j<=f+c&&o<=j)
dp[i][j][0]=min(dp[i][j][0],dp[i][j-o][0]+p[l]);
}
}
int ans=0x3f3f3f;
ans=min(dp[m-1][f-1][1],dp[m][f][0]);
if(ans!=0x3f3f3f)
cout<<ans<<endl;
else
cout<<"Impossible\n";
return 0;
}
我来个滚动数组，快3倍。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 300 + 24;
int m,f,r,c;
int dp[N][N][2];
int main()
{
scanf("%d%d%d%d",&m,&f,&r,&c);

memset(dp,0x3f3f3f3f,sizeof(dp));
dp[m][f][1] = dp[m][f][0] = 0;
for(int i = 0; i < r; i++)
{
int a,b;
scanf("%d%d",&a,&b);
for(int i = 0; i <= m; i++)
{
for(int j = 0; j <= f; j++)
{
int x1 = max(0,i-a);
int x2 = max(0,j-b);
dp[x1][j][0] = min(dp[x1][j][0],dp[i][j][0] + b);
dp[i][x2][0] = min(dp[i][x2][0],dp[i][j][0] + b);
dp[x1][j][1] = min(dp[x1][j][1],dp[i][j][1] + b);
dp[i][x2][1] = min(dp[i][x2][1],dp[i][j][1] + b);
if(i > 0 && j > 0 && a >= 2)
dp[i-1][j-1][1] = min(dp[i-1][j-1][1],dp[i][j][0] + b);
}
}
}
int d = min(dp[0][0][0],dp[0][0][1]);
if(d == 0x3f3f3f3f)
printf("Impossible");
else
printf("%d",d);
}

program vijosP1240;

var
     k1,k2,n,c:longint;
     b,p:array[1..300] of longint;
     f:array[0..300,0..300,0..300,0..1] of longint;
     ans:longint;

function min(a,b:longint):longint;
begin
     if a<b then
        exit(a)
     else
        exit(b);
end;

function max(a,b:longint):longint;
begin
     if a>b then
        exit(a)
     else
        exit(b);
end;

procedure init;
var
   i:longint;
begin
     readln(k1,k2,n,c);
     for i:=1 to n do
         readln(b[i],p[i]);
end;

procedure dp;
var
   i,t1,t2:longint;
begin
     ans:=maxlongint;
     fillchar(f,sizeof(f),127);
     for i:=0 to n do
         f[i,0,0,0]:=0;
     for i:=1 to n do
         for t1:=0 to k1 do
             for t2:=0 to k2 do
             begin
                  if (t1=0) and (t2=0) then continue;
                  f[i,t1,t2,0]:=min(f[i-1,max(0,t1-b[i]),t2,0]+p[i]
                                   ,f[i-1,t1,max(0,t2-b[i]),0]+p[i]);
                  f[i,t1,t2,0]:=min(f[i,t1,t2,0]
                                    ,f[i-1,t1,t2,0]);
                  //if c>=1 then
                  //begin
                  //f[i,t1,t2,1]:=min(f[i-1,max(0,t1-b[i]),t2,1]+p[i]
                  //                ,f[i-1,t1,max(0,t2-b[i]),1]+p[i]);
                  //f[i,t1,t2,1]:=min(f[i,t1,t2,1],f[i-1,t1,t2,1]);
                  //if (t1>0) and (t2>0) then
                  //f[i,t1,t2,1]:=min(f[i,t1,t2,1],f[i-1,t1-1,t2-1,0]+p[i]);
                  //end;
             end;
     for i:=1 to n do
         //for t1:=0 to 1 do
         //    if (t1=0) or ((t1=1) and (c>=1)) then
                ans:=min(ans,f[i,k1,k2,0]);
     if ans>=21*1000*1000 then
        writeln('impossible')
     else
        writeln(ans);
end;

begin
     init;
     dp;
end.

真是太诡异了我g[I][j][k] 打成了g[I][k][k]对了90分，改成g[I][j][k]居然0分！

···pascal
program vijosP1240;

var
k1,k2,n,c:longint;
b,p:array[1..300] of longint;
f:array[0..300,0..300,0..300,0..1] of longint;
ans:longint;

function min(a,b:longint):longint;
begin
if a<b then
exit(a)
else
exit(b);
end;

function max(a,b:longint):longint;
begin
if a>b then
exit(a)
else
exit(b);
end;

procedure init;
var
i:longint;
begin
readln(k1,k2,n,c);
for i:=1 to n do
readln(b[i],p[i]);
end;

procedure dp;
var
i,t1,t2:longint;
begin
ans:=maxlongint;
fillchar(f,sizeof(f),127);
for i:=0 to n do
f[i,0,0,0]:=0;
for i:=1 to n do
for t1:=0 to k1 do
for t2:=0 to k2 do
begin
if (t1=0) and (t2=0) then continue;
f[i,t1,t2,0]:=min(f[i-1,max(0,t1-b[i]),t2,0]+p[i]
,f[i-1,t1,max(0,t2-b[i]),0]+p[i]);
f[i,t1,t2,0]:=min(f[i,t1,t2,0]
,f[i-1,t1,t2,0]);
//if c>=1 then
//begin
//f[i,t1,t2,1]:=min(f[i-1,max(0,t1-b[i]),t2,1]+p[i]
// ,f[i-1,t1,max(0,t2-b[i]),1]+p[i]);
//f[i,t1,t2,1]:=min(f[i,t1,t2,1],f[i-1,t1,t2,1]);
//if (t1>0) and (t2>0) then
//f[i,t1,t2,1]:=min(f[i,t1,t2,1],f[i-1,t1-1,t2-1,0]+p[i]);
//end;
end;
for i:=1 to n do
//for t1:=0 to 1 do
// if (t1=0) or ((t1=1) and (c>=1)) then
ans:=min(ans,f[i,k1,k2,0]);
if ans>=21*1000*1000 then
writeln('impossible')
else
writeln(ans);
end;

begin
init;
dp;
end.
```

AC100留念，顺便说下这题数据有问题，考虑了夫妻反而WA....下面程序注释掉就是考虑夫妻的情况
'''pascal
program vijosP1240;

var
k1,k2,n,c:longint;
b,p:array[1..300] of longint;
f:array[0..300,0..300,0..300,0..1] of longint;
ans:longint;

function min(a,b:longint):longint;
begin
if a<b then
exit(a)
else
exit(b);
end;

function max(a,b:longint):longint;
begin
if a>b then
exit(a)
else
exit(b);
end;

procedure init;
var
i:longint;
begin
readln(k1,k2,n,c);
for i:=1 to n do
readln(b[i],p[i]);
end;

procedure dp;
var
i,t1,t2:longint;
begin
ans:=maxlongint;
fillchar(f,sizeof(f),127);
for i:=0 to n do
f[i,0,0,0]:=0;
for i:=1 to n do
for t1:=0 to k1 do
for t2:=0 to k2 do
begin
if (t1=0) and (t2=0) then continue;
f[i,t1,t2,0]:=min(f[i-1,max(0,t1-b[i]),t2,0]+p[i]
,f[i-1,t1,max(0,t2-b[i]),0]+p[i]);
f[i,t1,t2,0]:=min(f[i,t1,t2,0]
,f[i-1,t1,t2,0]);
if c>=1 then
begin
f[i,t1,t2,1]:=min(f[i-1,max(0,t1-b[i]),t2,1]+p[i]
,f[i-1,t1,max(0,t2-b[i]),1]+p[i]);
f[i,t1,t2,1]:=min(f[i,t1,t2,1],f[i-1,t1,t2,1]);
if (t1>0) and (t2>0) then
f[i,t1,t2,1]:=min(f[i,t1,t2,1],f[i-1,t1-1,t2-1,0]+p[i]);
end;
end;
for i:=1 to n do
for t1:=0 to 1 do
if (t1=0) or ((t1=1) and (c>=1)) then
ans:=min(ans,f[i,k1,k2,t1]);
if ans>=21*1000*1000 then
writeln('impossible')
else
writeln(ans);
end;

begin
init;
dp;
end.
'''

果然水题需细心。。
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int m, f, r, c, dp[305][305][305];
int b[305], p[305];
int main()
{
scanf("%d%d%d%d", &m, &f, &r, &c);
memset(dp, 127/3, sizeof dp);
for (int i = 1; i <= r; i++)
scanf("%d%d", &b[i], &p[i]);
dp[0][0][0] = 0; // 前i间j男k女
for (int i = 1; i <= r; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= f; k++) {
dp[i][j][k] = min(dp[i-1][j][k],
min(dp[i-1][max(j-b[i], 0)][k], dp[i-1][j][max(k-b[i], 0)])+p[i]);
if (j == 1 && k == 1 && c >= 1 && b[i] >= 2)
dp[i][j][k] = min(dp[i][j][k], dp[i-1][0][0]+p[i]);
}
if (dp[r][m][f] <= 10000000)
cout << dp[r][m][f] << endl;
else
cout << "Impossible" << endl;
return 0;
}

数据弱了吧？

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 300 + 24;
int m,f,r,c;
int dp[N][N][2];
int main()
{
#ifdef CDZSC_OFFLINE
freopen("in.txt","r",stdin);
#endif //CDZSC_OFFLINE
while(~scanf("%d%d%d%d",&m,&f,&r,&c))
{
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[m][f][1] = dp[m][f][0] = 0;
for(int i = 0; i < r; i++)
{
int a,b;
scanf("%d%d",&a,&b);
for(int i = 0; i <= m; i++)
{
for(int j = 0; j <= f; j++)
{
int x1 = max(0,i-a);
int x2 = max(0,j-a);
dp[x1][j][0] = min(dp[x1][j][0],dp[i][j][0] + b);
dp[i][x2][0] = min(dp[i][x2][0],dp[i][j][0] + b);
dp[x1][j][1] = min(dp[x1][j][1],dp[i][j][1] + b);
dp[i][x2][1] = min(dp[i][x2][1],dp[i][j][1] + b);
if(i > 0 && j > 0 && a >= 2)
dp[i-1][j-1][1] = min(dp[i-1][j-1][1],dp[i][j][0] + b);
}
}
}
int d = min(dp[0][0][0],dp[0][0][1]);
if(d == 0x3f3f3f3f)
printf("Impossible\n");
else
printf("%d\n",d);
}
}

/*【题解】
动态规划；
设f[i][j][k][0]表示前i个房间，男的放了j个女的放了k个的最优值，且没有夫妻在同一房间中
设f[i][j][k][1]表示前i个房间，男的。。。。。。。。。。。。。，且有一对夫妻在同一房间中。
为什么状态只有一对呢？
这是因为，如果有两对夫妻分别在不同的房间，那么完全可以将它们拆散，使得两男两女分别在两个不同的房间。这样可以使房间的
容量得到最大限度的利用。
转移方程
f[i][j][k][0]=min(f[i-1][j][k][0],f[i-1][j-v][k][0]+pi,f[i-1][j][k-v][0]+pi);
f[i][j][k][1]=min(f[i-1][j][k][1],f[i-1][j-1][k-1][0]+pi,f[i-1][j-v][k][1]+pi,f[i-1][j][k-v][1]+pi);
注意不要漏掉状态，否则前功尽弃！
至于网上流传的一个三维的数组，请试试以下数据。
【*test.in】
6 6 5 2
2 5
2 6
3 5
5 1
5 2
【*test.out】
8
这是我在测试网上流传的题解程序时发现的问题，程序会出现10以上的解。
*/

#include <iostream>
#include <cstring>
using namespace std;
int m,f,r,c,b[301],p[301],ff[301][301][301][2];
int main()
{
cin>>m>>f>>r>>c;
for (int i=1;i<=r;i++)
cin>>b[i]>>p[i];
memset(ff,127,sizeof(ff));
int temp=ff[0][0][1][1],ans=temp;
ff[0][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--)
{
if (b[i]>=2 && j>=1 && k>=1)
ff[i][j][k][1]=min(ff[i-1][j-1][k-1][0]+p[i],ff[i-1][j][k][1]);
ff[i][j][k][0]=min(ff[i][j][k][0],ff[i-1][j][k][0]);
for (int t=1;t<=b[i];t++)
{
if (j-t>=0)
{
ff[i][j][k][0]=min(ff[i][j][k][0],ff[i-1][j-t][k][0]+p[i]);
ff[i][j][k][1]=min(ff[i][j][k][1],ff[i-1][j-t][k][1]+p[i]);
}
if (k-t>=0)
{
ff[i][j][k][0]=min(ff[i][j][k][0],ff[i-1][j][k-t][0]+p[i]);
ff[i][j][k][1]=min(ff[i][j][k][1],ff[i-1][j][k-t][1]+p[i]);
}
}
}
ans=min(ff[r][m][f][0],ff[r][m][f][1]);
if (ans==temp) cout <<"Impossible"<<endl;else cout<<ans<<endl;
return 0;
}

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

测试数据 #0: Accepted, time = 0 ms, mem = 900 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 896 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 896 KiB, score = 10

测试数据 #3: Accepted, time = 171 ms, mem = 892 KiB, score = 10

测试数据 #4: Accepted, time = 187 ms, mem = 896 KiB, score = 10

测试数据 #5: Accepted, time = 171 ms, mem = 896 KiB, score = 10

测试数据 #6: Accepted, time = 171 ms, mem = 892 KiB, score = 10

测试数据 #7: Accepted, time = 171 ms, mem = 892 KiB, score = 10

测试数据 #8: Accepted, time = 156 ms, mem = 896 KiB, score = 10

测试数据 #9: Accepted, time = 171 ms, mem = 892 KiB, score = 10

orz楼上神牛

又被题目坑了

这题根本不需要考虑夫妻同房，考虑了就WA！

强烈鄙视出题人

方程写错了，结果全过了。。。

正确做法要考虑夫妻。

易知最多只能有一对夫妇一个房间

设

f表示前i个房间住j名男性k名女性并且没有夫妇住在一起的最小花费

f表示前i个房间住j名男性k名女性并且有一对夫妇住在一起的最小花费

则

f=min(f,f+p[i],f+p[i])

f=min(f,f+p[i],f[i-1,j,k-v[i],1+p[i],f+p[i])

约束条件很多要小心。

http://blog.sina.com.cn/s/blog_5774b8650100fv1b.html

没有考虑夫妻，直接二维背包

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

万慢