题意：

有$n$个男人，$m$个女人一起住宿，其中有$r$个房间，这些人中有$c$对夫妇。每对夫妇在一间房间的时候房间不能有其他人，不是一对的男女不能同房。没有一夫多妻、一妻多夫。每个房间有容量$bi$，有费用$pi$。请问让全部人住进去最少需要多少钱。

思路：

如果有两对夫妇的话，分别需要$2+2$的房间，如果把他们分成$2$男$2$女，也是分成$2+2$的房间，且房间还可能住其他人，所以显然更优，所以最优的情况下最多只有$c$的夫妇住在一起，那么只要用动态规划计算没有夫妻住在一起的情况和只有一对夫妻住在一起的情况就行了。用$f[i][j]$表示$i$个男人，$j$个女人住在旅馆里最少需要多少钱。思路很简单，直接看代码就能懂了。

标程

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 515
#define inf 0x3f3f3f3f
typedef long long LL;
int T,n,m,r,c,ans;
int b[maxn],p[maxn],f[maxn][maxn];

void init()
{
    scanf("%d%d%d%d",&n,&m,&r,&c);
    for (int i=1;i<=r;++i)
        scanf("%d%d",&b[i],&p[i]);
}

void updata(int&x ,int y)
{
    if (y<x) x=y;
}

void solve()
{
    int tb,tp,tans,tk;
    ans=inf;
    for (int i=0;i<=n+10;++i)
        memset(f[i],0x3f,(m+10)*4);
    f[0][0]=0;
    for (int i=1;i<=r;++i)
    {
        tb=b[i];tp=p[i];    
        for (int t1=n+5;t1>=0;t1--)
            for (int t2=m+5;t2>=0;t2--)
            {
                if (tb<=t1) updata(f[t1][t2],f[t1-tb][t2]+tp);
                if (tb<=t2) updata(f[t1][t2],f[t1][t2-tb]+tp);
            }
    }
    for (int i=n;i<=n+5;++i)
        for (int j=m;j<=m+5;++j)
            ans=min(ans,f[i][j]);
    if (c%2==0) return;
    tk=0;
    b[0]=6;p[0]=inf;
    for (int i=1;i<=r;++i)
        if (b[i]>=2  && (p[i]<=p[tk] || (p[i]==p[tk] && b[i]<b[tk])))
            tk=i;
    if (!tk) return;
    n--;m--;
    for (int i=0;i<=n+10;++i)
        memset(f[i],0x3f,(m+10)*4);
    f[0][0]=0;
    for (int i=1;i<=r;++i)
    {
        if (i==tk) continue;
        tb=b[i];tp=p[i];    
        for (int t1=n+5;t1>=0;t1--)
            for (int t2=m+5;t2>=0;t2--)
            {
                if (tb<=t1) updata(f[t1][t2],f[t1-tb][t2]+tp);
                if (tb<=t2) updata(f[t1][t2],f[t1][t2-tb]+tp);
            }
    }
    for (int i=n;i<=n+5;++i)
        for (int j=m;j<=m+5;++j)
            ans=min(ans,f[i][j]+p[tk]);
}

int main()
{
    scanf("%d",&T);
    for (int i=1;i<=T;++i)
    {
        init();
        solve();
        if (ans!=inf) printf("%d\n",ans);
        else printf("Impossible\n");
    }
    return 0;
}