📋 个人简介

🎉大家好，我是3月份新人榜排名第三的 ༺Blog༒Hacker༻
💬支持我：点赞👍+收藏⭐️+留言📝
🌺格言：༺永做优质༒programmer༻

📣 又要写不完作业了！

题目背景

寒假将近尾声，又双叒叕写不完作业了！！！ 本题是一个非常实际的问题，可能能帮助你解决困境（如果解决了困境，别忘了请出题人吃饭）

题目描述

现在你有n本作业，每本作业有一个科目k，每本需要t的时间写完，但是你发现你总共只剩下了tot的时间

显然，由于你沉迷竞赛，“荒废”了大半个假期，作业很可能写不完了

但是每课老师都非常在乎自己科的作业情况，所以当你该科有x项作业没交时，他/她就会对你发hx的火(保证hx随x增加不降)

当然，如果你完成了该科所有作业，老师就不会对你发火

另外，你至少需要写m本作业，否则你会被班主任请家长！

所以你需要仔细思考完成你的哪些作业，以让所有老师对你发的火的和最小（）

输入格式

第一行三个正整数n,m,tot 然后一行n个整数表示h1~hn 然后n行，其中第i行的两个整数表示第i项作业的k,t 输出格式
如果你不能完成m本即以上的作业，输出一行一个字符串"You are over!"(不带引号)

否则输出一行一个整数表示所有老师对你发的火的最小的和

输入样例14 1 11 10 100 10001 12 22 32 100输出样例1100输入样例24 2 61 10 100 10001 42 22 32 100输出样例22输入样例34 4 11 10 100 10001 12 22 32 100输出样例3You are over!输入样例410 4 81 10 100 1000 1001 1002 1003 1004 1005 10061 12 11000000000 11 11 11 21 71 82 42 5输出样例420输入样例510 4 81 10 11 1000 1001 1002 1003 1004 1005 10061 12 11000000000 11 11 11 81 21 72 42 5输出样例513输入样例65 3 31 10 100 1000 50001 11 31 22 13 1输出样例610

样例解释样例5:写第1,2,4,5,9本作业,超过4本作业剩下第1科有3本作业没写(6,7,8)，第2课有1本作业没写，第1000000000有1本作业没写所以你被发了11+1+1的火（看样子1大概是语文，2大概是数学，1000000000大概是美术）

数据范围对于50%的数据1≤k≤100,1≤tot≤500对于100%的数据1≤m≤n≤100,1≤t≤100,1≤k≤109,1≤tot,hi≤5000Limits1s,64MB

💯CODE

#include #define for1(i,n) for(i=1;i<=(n);i++)#define for0n(i,n) for(i=0;i<=(n);i++)#define forlr(i,l,r) for(i=(l);i<=(r);i++)using namespace std;const int T=5005,N=105;int dp1[N][T],dp2[N][T],h[N],n,m,tot,ck,a[N][N],ca[N],ans=1e9;unordered_map<int,int> map1;int main(){scanf("%d%d%d",&n,&m,&tot);int i,j,k,x,y;for1(i,n) scanf("%d",&h[i]);for1(i,n){scanf("%d%d",&x,&y);int &mx=map1[x];if(!mx) mx=++ck;a[mx][++ca[mx]]=y;}memset(dp1,0x1f,sizeof(dp1));memset(dp1[0],0,sizeof(dp1[0]));for1(i,ck){memset(dp2,0x1f,sizeof(dp2));sort(a[i]+1,a[i]+ca[i]+1);for1(j,ca[i]) a[i][j]+=a[i][j-1];for0n(j,ca[i]) forlr(k,j,n) forlr(x,a[i][j],tot)dp2[k][x]=min(dp2[k][x],dp1[k-j][x-a[i][j]]+h[ca[i]-j]);memcpy(dp1,dp2,sizeof(dp1));}forlr(i,m,n) ans=min(ans,dp2[i][tot]);if(ans>1e8) printf("You are over!\n");else printf("%d\n",ans);return 0;}

🔮朋友们，点赞是我更新的动力，明天再见，拜拜！！！

UCloud