CF1271D Portals

題意：

題意選自洛谷

題解：

首先要先發現性質：對于任何一個城堡u，如果要往u駐軍，則在攻占編號最大的能向u行軍的城堡后再駐軍，答案一定不會變劣。你想想，如果后面有編號更大的點可以前往u，那我們就沒有必要再之前派軍駐扎，如果派軍反而還會少一個士兵。因此對于一個城堡，我們只需要保存編號最大的城堡到他的行軍路線。一開始每個城堡到其編號最大的城堡是其本身
現在考慮dp轉移，感覺本題情況非常多又復雜。我們可以規整規整，因為攻打順序是1到n，順序已經給好了，那么對于第i個點，我們可以派軍駐扎其能到達的點，也可以不派軍駐扎。這是兩個大的狀態，由此設dp[i][j]表示當前在第i個點，士兵的數量為j的最大分數。dp初始化為負無窮
當從第i-1個點到第i個點時，我們需要考慮第i個點新增的部隊數量，需要考慮第i個點是否要去其他點派軍，顯然為了最優，派軍去x個點只需要x個兵
假設第i個點可以往num個點派軍，那我們對這num個價值排序，因為我們必然是優先去價值高的，sum[x]:表示去價值最高得x個點派軍所得價值，這可以用優先隊列+前綴和來實現
那么狀態轉移方程為：
dp[i][j+b[i]-x]=max(dp[i][j+b[i]-x],dp[i-1][j]+sum[x]);
i枚舉的是當前所處點
j是當前軍隊，b[i]是第i個點可以新增的部隊數量，x是所派士兵數量(派軍去了x個點)，當x=0時為任何點都不占領(包含當前所在點)
這樣轉移看似復雜度是$O(n^3)$，實則是均攤為$O(n^2)$
詳細看代碼

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; bool Handsome; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test(bool &Most) { #ifdef ONLINE_JUDGE #elseprintf("%.2lfMB\n",(&Most-&Handsome)/1024.0/1024.0);startTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=5000+9; int dp[maxn][maxn]; priority_queue<int>q; int a[maxn],b[maxn],c[maxn]; int sum[maxn]; int maxx[maxn]; vector<int>vec[maxn]; int add[maxn]; bool Most; int main() { // rd_test(Most);int n,m,k;read(n,m,k);memset(dp,-INF_int,sizeof(dp));dp[0][k]=0;int f=0;for(int i=1;i<=n;i++){read(a[i],b[i],c[i]);if(add[i-1]+k<a[i])f=1;add[i]=add[i-1]+b[i];maxx[i]=i;}for(int i=1;i<=m;i++){int u,v;read(u,v);maxx[v]=max(maxx[v],u);}for(int i=1;i<=n;i++){vec[maxx[i]].push_back(i);}if(f){puts("-1");return 0;}for(int i=1;i<=n;i++){while(!q.empty())q.pop();for(auto v:vec[i]){q.push(c[v]);}int num=0;for(int i=1;i<=n;i++)sum[i]=0;while(!q.empty()){num++;if(num==1)sum[num]=q.top();else sum[num]=sum[num-1]+q.top();q.pop();}for(int j=a[i];j+b[i]<=k+add[i];j++){if(dp[i-1][j]<0)continue;for(int x=0;x<=num;x++){dp[i][j+b[i]-x]=max(dp[i][j+b[i]-x],dp[i-1][j]+sum[x]);}}}int MAX=0;for(int i=0;i<=k+add[n];i++)MAX=max(MAX,dp[n][i]);cout<<MAX<<endl;Time_test(); }

總結

以上是生活随笔為你收集整理的CF1271D Portals的全部內容，希望文章能夠幫你解決所遇到的問題。

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