打卡信奥刷题（2549）用C++实现信奥 P2113 看球泡妹子-编程实验室

P2113 看球泡妹子

题目背景

2014 年巴西世界杯开幕了，现在满城皆是世界杯，商家们利用它大赚一笔，小明和小红也借此机会增进感情。

题目描述

本届世界杯共有nnn支球队，mmm场比赛。男球迷小明喜欢看比赛，女球迷小红喜欢看帅哥。每支球队在小明眼里的实力值为aia_iai，在小红眼里的帅哥数量为bib_ibi。

每场比赛有两个球队对抗，它们的编号分别是pip_ipi和qiq_iqi。小明认为一场比赛的精彩度等于两队实力的乘积，小红则认为是两队帅哥数量之和。

由于体力的限制，他们最多只能看kkk场比赛。当然，只要看比赛，两个人一定会一起看。小明作为男生，理应迁就一下女生，所以，请你写一个程序，求出小红看到比赛的精彩度总和不小于ccc的情况下，小明看到比赛的精彩度的最大总和。

输入格式

第一行包含四个正整数n,m,k,cn,m,k,cn,m,k,c。

第二行有nnn个用空格隔开的正整数aia_iai。

第三行有nnn个用空格隔开的正整数bib_ibi。

接下来mmm行，每行两个正整数pi,qip_i,q_ipi,qi。

输出格式

一行，一个正整数表示小明看到比赛的精彩度的最大总和。如果无论如何都无法满足小红的要求，输出-1。

输入输出样例 #1

输入 #1

4 3 2 5 2 2 1 3 1 1 1 2 1 2 2 3 3 4

输出 #1

说明/提示

数据范围与约定

对于20%20\%20%数据，1≤n,m,k≤51 \le n,m,k \le 51≤n,m,k≤5。
对于100%100\%100%数据，1≤n≤1001 \le n \le 1001≤n≤100，1≤k≤m≤1001 \le k \le m \le 1001≤k≤m≤100，1≤ai,bi≤101 \le a_i,b_i \le 101≤ai,bi≤10，1≤c≤1031 \le c \le 10^31≤c≤103。

C++实现

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintN=110;intp[N],q[N],a[N],b[N],dp[N][N][20*N];intmain(){intn,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*mdp[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][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;elsecout<<-1<<endl;return0;}