I love exam

不知道為啥剛開始不寫，那么簡單的背包預處理dp，太菜了吧

$f_{i,j}$對于第i門課來說花費j天得到的最大分數

$g_{i,j,p}$考慮前i門課，花費j天復習得到的最大分數

#include<bits/stdc++.h> using namespace std; using ll=long long; using pii=pair<int,int>; using pli=pair<ll,int>; constexpr ll mod=1e9+7; //============================= int rd() {int res=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res; } unordered_map<string,int> mp;int id; vector<pair<int,int>> a[55]; int n,m; int f[55][505]; int g[55][505][4]; int T,P; void init() {mp.clear();id=0;memset(f,-0x3f,sizeof f);memset(g,-0x3f,sizeof g);for(int i=1;i<=n;i++) a[i].clear(); } int main() {int Tc=rd();while(Tc--){init();n=rd();for(int i=1;i<=n;i++){string s;cin>>s;mp[s]=++id;}m=rd();for(int i=1;i<=m;i++){string s;cin>>s;int w=rd(),v=rd();a[mp[s]].push_back({v,w});}T=rd(),P=rd();for(int i=1;i<=n;i++){f[i][0]=0;for(auto t:a[i]){int v=t.first,w=t.second;for(int j=T;j>=v;j--) f[i][j]=min(100,max(f[i][j],f[i][j-v]+w));}}g[0][0][0]=0;for(int i=1;i<=n;i++)for(int j=0;j<=T;j++)for(int p=0;p<=P;p++)for(int k=0;k<=j;k++){if(f[i][k]>=60)g[i][j][p]=max(g[i][j][p],g[i-1][j-k][p]+f[i][k]);else{if(p) g[i][j][p]=max(g[i][j][p],g[i-1][j-k][p-1]+f[i][k]);}}int ans=-1;for(int p=0;p<=P;p++) ans=max(ans,g[n][T][p]);printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的2021“MINIEYE杯”中国大学生算法设计超级联赛（2）I love exam（背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。