首页 > 代码库 > hihocoder1386 Pick Your Players(dp)
hihocoder1386 Pick Your Players(dp)
题意:
你需要买一个足球队(11个球员),每个球员有位置、价值。花费,有以下限制:
位置分为前锋(1-3人)、中腰(2-5)、后卫(3-5)、守门员(1)
每个人有 value
,总的 value
是每个人的value
加起来 ,选一个队长,队长的加两次
每个人有个 cost
,总花费不能超过给定值
求:最大的 value
,相应的最小的 cost
,相应的购买方案数(大于1e9输出1e9)
10组数据,500个候选人,value 和 cost:V and C (0 <= V <= 1000, 0 <= C <= 1000),花费上界:1000
思路:
考虑dp(i,cost,j,k,r,w)=(value,way)
表示考虑前i
个球员,
费用和为cost
,选了j
个前锋k
个中腰r
个后卫w
个守门员这个状态,价值和是value
,方案数是way。
然后按照dp字面意思转移就可以了。然后第一维的iii
这里是为了看起来方便,其实是不用开的。
为了方便处理队长,把球员们按照价值从大到小排序,挑的第一个人当队长就可以了。
以上取自ICPCCAMP题解
然后我就照着写了一发,怎么调都wa,感觉对对的- -
先存着吧,等以后或许有题解了再对比一下
可以把set换成vector+bool矩阵少一个log复杂度~
有哪位聚聚看出来问题请通知我~感激不尽
/* ***********************************************Author :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <stack>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){ char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-‘0‘; c=getchar(); }}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9;const int N=1e3+10;pair<int,LL> dp[N][4][6][6][2];struct wq{ char s[12]; int val,cost;} a[510];bool cmp(wq a,wq b){ return a.val>b.val;}set<int>eg[1500];int main(){ int t,n,all; rd(t); while(t--) { rd(n); rep(i,1,n) scanf("%s",a[i].s),rd(a[i].val),rd(a[i].cost); rd(all); sort(a+1,a+n+1,cmp); memset(dp,0,sizeof(dp)); int ansval=0,anscost=0; rep(i,0,1400) eg[i].clear(); LL anssum=0; rep(i,1,n) { if(a[i].s[0]==‘F‘) { dep(f,3,1)dep(m,5,0)dep(d,5,0)dep(g,1,0) { int hs=(f-1)*100+m*10+d+g*1000; if(f+m+d+g>11||eg[hs].size()==0) continue; for(auto j:eg[hs]) { int c=j+a[i].cost; if(c>all) continue; if(dp[c][f][m][d][g].first<dp[c-a[i].cost][f-1][m][d][g].first+a[i].val) { dp[c][f][m][d][g].first=dp[c-a[i].cost][f-1][m][d][g].first+a[i].val; dp[c][f][m][d][g].second=dp[c-a[i].cost][f-1][m][d][g].second; eg[hs+100].insert(c); } else if(dp[c][f][m][d][g].first==dp[c-a[i].cost][f-1][m][d][g].first+a[i].val) { dp[c][f][m][d][g].second+=dp[c-a[i].cost][f-1][m][d][g].second; if(dp[c][f][m][d][g].second>mod) dp[c][f][m][d][g].second=mod; eg[hs+100].insert(c); } } } if(a[i].val*2>dp[a[i].cost][1][0][0][0].first) { dp[a[i].cost][1][0][0][0].first=a[i].val*2; dp[a[i].cost][1][0][0][0].second=1; eg[100].insert(a[i].cost); } else if(a[i].val*2==dp[a[i].cost][1][0][0][0].first) { dp[a[i].cost][1][0][0][0].second++; eg[100].insert(a[i].cost); } } else if(a[i].s[0]==‘M‘) { dep(m,5,1)dep(f,3,0)dep(d,5,0)dep(g,1,0) { int hs=f*100+(m-1)*10+d+g*1000; if(f+m+d+g>11||eg[hs].size()==0) continue; for(auto j:eg[hs]) { int c=j+a[i].cost; if(c>all) continue; if(dp[c][f][m][d][g].first<dp[c-a[i].cost][f][m-1][d][g].first+a[i].val) { dp[c][f][m][d][g].first=dp[c-a[i].cost][f][m-1][d][g].first+a[i].val; dp[c][f][m][d][g].second=dp[c-a[i].cost][f][m-1][d][g].second; eg[hs+10].insert(c); } else if(dp[c][f][m][d][g].first==dp[c-a[i].cost][f][m-1][d][g].first+a[i].val) { dp[c][f][m][d][g].second+=dp[c-a[i].cost][f][m-1][d][g].second; if(dp[c][f][m][d][g].second>mod) dp[c][f][m][d][g].second=mod; eg[hs+10].insert(c); } } } if(a[i].val*2>dp[a[i].cost][0][1][0][0].first) { dp[a[i].cost][0][1][0][0].first=a[i].val*2; dp[a[i].cost][0][1][0][0].second=1; eg[10].insert(a[i].cost); } else if(a[i].val*2==dp[a[i].cost][0][1][0][0].first) { dp[a[i].cost][0][1][0][0].second++; eg[10].insert(a[i].cost); } } else if(a[i].s[0]==‘D‘) { dep(d,5,1)dep(f,3,0)dep(m,5,0)dep(g,1,0) { int hs=f*100+m*10+d-1+g*1000; if(f+m+d+g>11||eg[hs].size()==0) continue; for(auto j:eg[hs]) { int c=j+a[i].cost; if(c>all) continue; if(dp[c][f][m][d][g].first<dp[c-a[i].cost][f][m][d-1][g].first+a[i].val) { dp[c][f][m][d][g].first=dp[c-a[i].cost][f][m][d-1][g].first+a[i].val; dp[c][f][m][d][g].second=dp[c-a[i].cost][f][m][d-1][g].second; eg[hs+1].insert(c); } else if(dp[c][f][m][d][g].first==dp[c-a[i].cost][f][m][d-1][g].first+a[i].val) { dp[c][f][m][d][g].second+=dp[c-a[i].cost][f][m][d-1][g].second; if(dp[c][f][m][d][g].second>mod) dp[c][f][m][d][g].second=mod; eg[hs+1].insert(c); } } } if(a[i].val*2>dp[a[i].cost][0][0][1][0].first) { dp[a[i].cost][0][0][1][0].first=a[i].val*2; dp[a[i].cost][0][0][1][0].second=1; eg[1].insert(a[i].cost); } else if(a[i].val*2==dp[a[i].cost][0][0][1][0].first) { dp[a[i].cost][0][0][1][0].second++; eg[1].insert(a[i].cost); } } else { dep(f,3,0)dep(m,5,0)dep(d,5,0) { int hs=f*100+m*10+d; if(f+m+d+1>11||eg[hs].size()==0) continue; for(auto j:eg[hs]) { int c=j+a[i].cost; if(c>all) continue; if(dp[c][f][m][d][1].first<dp[c-a[i].cost][f][m][d][0].first+a[i].val) { dp[c][f][m][d][1].first=dp[c-a[i].cost][f][m][d][0].first+a[i].val; dp[c][f][m][d][1].second=dp[c-a[i].cost][f][m][d][0].second; eg[hs+1000].insert(c); } else if(dp[c][f][m][d][1].first==dp[c-a[i].cost][f][m][d][0].first+a[i].val) { dp[c][f][m][d][1].second+=dp[c-a[i].cost][f][m][d][0].second; if(dp[c][f][m][d][1].second>mod) dp[c][f][m][d][1].second=mod; eg[hs+1000].insert(c); } } } if(a[i].val*2>dp[a[i].cost][0][0][0][1].first) { dp[a[i].cost][0][0][0][1].first=a[i].val*2; dp[a[i].cost][0][0][0][1].second=1; eg[1000].insert(a[i].cost); } else if(a[i].val*2==dp[a[i].cost][0][0][0][1].first) { dp[a[i].cost][0][0][0][1].second++; eg[1000].insert(a[i].cost); } } //printf("%d\n",i); //rep(f,0,3)rep(m,0,5)rep(d,0,5)rep(g,0,1)rep(c,0,all) if(dp[c][f][m][d][g].second) printf("%d %c %d %d %d %d %d %d %lld\n",i,a[i].s[0],f,m,d,g,c,dp[c][f][m][d][g].first,dp[c][f][m][d][g].second); //system("pause"); } rep(f,1,3)rep(m,2,5)rep(d,3,5) { if(f+m+d<10) continue; if(f+m+d>10) break; int hs=f*100+m*10+d+1000; //printf("%d %d\n",hs,eg[hs].size()); if(!eg[hs].size()) continue; for(auto j:eg[hs]) { int c=j; //printf("%d %d %lld\n",c,dp[c][f][m][d][1].first,dp[c][f][m][d][1].second); if(dp[c][f][m][d][1].first>ansval) { ansval=dp[c][f][m][d][1].first; anscost=c; anssum=dp[c][f][m][d][1].second; } else if(dp[c][f][m][d][1].first==ansval) { if(c<anscost) { anscost=c; anssum=dp[c][f][m][d][1].second; } else if(c==anscost) { anssum+=dp[c][f][m][d][1].second; if(anssum>mod) anssum=mod; } } } } if(anssum>mod) anssum=mod; printf("%d %d %lld\n",ansval,anscost,anssum); } return 0;}
hihocoder1386 Pick Your Players(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。