传送门
题意：给\(s\)个玩家，\(n\)个城堡，\(m\)个士兵，每一个玩家向每一个城堡派出士兵数量已知，你要赢某个玩家的条件是你在这个城堡派出了大于这个玩家派出士兵数量的两倍，这个时候你在第\(i\)个城堡就会获得\(i\)分，你有\(m\)个士兵，问你最大分数是多少
解答：将每一个城堡看成一组，然后sort一遍了过后，那么你的花费大于第\(j\)个玩家的两倍的话，你在这一组里面的得分就是\((j+1)*(k+1)\)（\(j\)和\(k\)都是从0开始的）这样就可以使用分组背包求解，每一个物品的重量相当于\(a[k][j]*2+1\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 12/30/2019 11:03:37 PM *************************************************************************/ //#pragma GCC optimize(2) //#pragma GCC diagnostic error "-std=c++11" #include <cstring> #include <cmath> #include <cstdio> #include <cctype> #include <cstdlib> #include <ctime> #include <vector> #include <iostream> #include <string> #include <queue> #include <set> #include <map> #include <algorithm> #include <complex> #include <stack> #include <bitset> #include <iomanip> #include <list> #include <sstream> #include <fstream> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define endl '\n' #define ALL(x) x.begin(),x.end() #define MP(x,y) make_pair(x,y) #define ll long long #define ull unsigned long long #ifdef WindCry1 #define DEBUG(x) cout<<#x<<" : "<<x<<endl; #endif #define lowbit(x) x&(-x) #define ls u<<1 #define rs u<<1|1 using namespace std; template<typename T> inline T MIN(const T &a,const T &b) {return a<b?a:b;} template<typename T> inline T MAX(const T &a,const T &b) {return a>b?a:b;} template<typename T,typename ...Args> inline T MIN(const T &a,const T &b,Args ...args) {return MIN(MIN(a,b),args...);} template<typename T,typename ...Args> inline T MAX(const T &a,const T &b,Args ...args) {return MAX(MAX(a,b),args...);} typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<double,double> pdd; const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int mod = 1e9+7; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; int dp[20010]; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #ifdef WindCry1 freopen("C:/Users/LENOVO/Desktop/in.txt","r",stdin); #endif int s,n,m;cin>>s>>n>>m; vector<vector<int> > a(n); for(int i=0;i<s;i++) { for(int j=0,t;j<n;j++) cin>>t,a[j].push_back(t); } for(int k=0;k<n;k++){ sort(ALL(a[k])); for(int i=m;i>=0;i--) for(int j=0;j<s;j++){ if(i>=a[k][j]*2+1){ dp[i]=max(dp[i],dp[i-a[k][j]*2-1]+(j+1)*(k+1)); } } } cout<<dp[m]<<endl; return 0; } |
0 条评论