打卡信奥刷题（3119）用C++实现信奥题 P7381 [COCI 2018/2019 #6] Sličice

P7381 [COCI 2018/2019 #6] Sličice题目描述Nikola 喜欢收集足球队员的照片并将其保存在相册中。他计划收集N NN支球队的队员照片其中每支球队都有M MM张。对于 Nikola 所收集的每支球队该球队的照片数量x xx能给他增加分数B x B_xBx​。他目前拥有球队i ii的照片数量为P i P_iPi​。Nikola 的好朋友 Ivan 有两套完整的相册。Ivan 决定送K KK张照片给 Nikola。Nikola 想要知道在得到这K KK张照片之后它的相册所能得到的分数的最大值。输入格式第一行输入整数N , M , K N,M,KN,M,K。第二行输入N NN个整数P i P_iPi​。第三行输入M 1 M1M1个整数B i B_iBi​其中B i B_iBi​表示一支球队收集到了i ii张不同的照片能够获得B i B_iBi​分。对于[ 0 , M − 1 ] [0,M-1][0,M−1]内的每一个整数t tt都满足B t ≤ B t 1 B_t \le B_{t1}Bt​≤Bt1​。同时K ≤ N × M − ∑ i 1 N P i K \le N \times M-\sum_{i1}^N P_iK≤N×M−∑i1N​Pi​。输出格式输出能够得到的分数的最大值。输入输出样例 #1输入 #14 4 3 4 2 3 1 0 1 3 6 10输出 #131输入输出样例 #2输入 #24 3 5 1 1 2 3 0 1 2 3输出 #212输入输出样例 #3输入 #33 6 2 2 4 1 31 38 48 60 75 91 120输出 #3206说明/提示样例 1 解释Nikola 一开始拥有球队1 , 2 , 3 , 4 1,2,3,41,2,3,4照片数量分别为4 , 2 , 3 , 1 4,2,3,14,2,3,1。最优的方案是获得球队2 22照片2 22张球队1 11一张。此时分数最大为10 10 10 1 31 101010131101010131。数据规模与约定对于20 % 20\%20%的数据K 2 K2K2。对于100 % 100\%100%的数据1 ≤ N , M ≤ 500 1 \le N,M \le 5001≤N,M≤5001 ≤ K ≤ min ⁡ ( N × M , 500 ) 1 \le K \le \min(N \times M,500)1≤K≤min(N×M,500)0 ≤ P i ≤ M 0 \le P_i \le M0≤Pi​≤M0 ≤ B i ≤ 10 5 0 \le B_i \le 10^50≤Bi​≤105。说明本题分值按 COCI 原题设置满分90 9090。题目译自 COCI2018-2019 CONTEST #6T3 Sličice。C实现#includeiostreamusingnamespacestd;constintMAXN5005;longlongp[MAXN],b[MAXN],n,m,k,sum,dp[MAXN][MAXN];intmain(){cinnmk;for(inti1;in;i){cinp[i];}for(inti0;im;i){cinb[i];}for(inti1;in;i){//前i个球队for(intj0;jk;j){//一共用去j张照片for(intl0;lj;l){//第i个球队用l张照片if(p[i]lm){//如果超出范围break;//跳出}dp[i][j]max(dp[i][j],dp[i-1][j-l]b[p[i]l]);//取最大值}}}coutdp[n][k];//输出return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容