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
7说明/提示
数据范围与约定
- 对于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;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容