题解 P2113 【看球泡妹子】

TheGod · 2017-10-23 21:30:35 · 题解

（题目名称与背景成功吸引了我）

每两个队伍的比赛可以看做一个重量b[p[i]]+b[q[i]]，价值a[p[i]]*a[q[i]]的物品

转化为最多选k次的01背包

dp[i][t][j]表示 已经选i个，本次选到了第t个，小红满意度j时 小明的最大满意度

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110;
int p[N],q[N],a[N],b[N],dp[N][N][20*N];
int main(){
    int n,m,i,j,t,k,c,ans=0;
    scanf("%d%d%d%d",&n,&m,&k,&c);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=n;i++)scanf("%d",&b[i]);
    for(i=1;i<=m;i++)scanf("%d%d",&p[i],&q[i]);
    memset(dp,0,sizeof(dp));
    for(i=1;i<=k;i++)
       for(t=i;t<=m;t++)
           for(j=20*m;j>=0;j--){//Ai<=10，上界2*10*m
               dp[i][t][j]=max(dp[i][t][j],dp[i][t-1][j]);
               if(j>=b[p[t]]+b[q[t]])
                   if(dp[i-1][t-1][j-b[p[t]]-b[q[t]]]>0||j==b[p[t]]+b[q[t]])
                   //dp[i-1][t-1][j-b[p[t]]-b[q[t]]]的状态可以到达 或者 第一次选
                  //第一次选的状态也可以在dp前预处理
                       dp[i][t][j]=max(dp[i][t][j],
                       dp[i-1][t-1][j-b[p[t]]-b[q[t]]]+a[p[t]]*a[q[t]]);
               if(j>=c)ans=max(ans,dp[i][t][j]);}
    if(ans>0)cout<<ans<<endl;
        else cout<<-1<<endl;
return 0;}