題目鏈接

https://atcoder.jp/contests/agc032/tasks/agc032_d

題解

又是一道神仙題啊啊啊啊。。。atcoder題真的做不來啊QAQ

第一步又是神仙轉化: 對于把第一個挪到最后其他左移這件事情，可以轉化為把第一個挪到最后和最后的下一個之間的某個位置(非整數)，右移同理。
于是問題就變成了: 有\(N\)個數一開始每個數有個位置，現在可以花\(A\)的代價把一個數往右移到任意位置(不一定非是整數)，\(B\)的代價把一個數往左移到任意位置，然后求將它們排序的最小代價和！

這個東西又是一個簡單的dp，設\(dp[i][j]\) (\(0\le j\le n\))表示前\(i\)個數排好序，第\(i\)個放在區間\([j,j+1)\)內的最小代價，轉移非常容易(注意要對不移動的情況單獨考慮)，前綴和優化，時間復雜度\(O(N^2)\).

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 5000; const llong INF = 10000000000000000ll; int p[N+3],pp[N+3]; llong dp[N+3][N+5],sdp[N+3][N+5]; int n; llong arga,argb;void update(llong &x,llong y) {x = x<y?x:y;}int main() {scanf("%d%lld%lld",&n,&arga,&argb);for(int i=1; i<=n; i++) {scanf("%d",&p[i]); pp[p[i]] = i;}for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) dp[i][j] = sdp[i][j] = INF;for(int i=0; i<=n; i++) sdp[0][i] = dp[0][i] = 0ll;for(int i=1; i<=n; i++){for(int j=0; j<=n; j++){if(j==pp[i]) {update(dp[i][j],sdp[i-1][j-1]);}llong tmp = sdp[i-1][j]+(j<pp[i]?argb:arga);update(dp[i][j],tmp); // printf("dp[%d][%d]=%lld\n",i,j,dp[i][j]);}sdp[i][0] = dp[i][0];for(int j=1; j<=n; j++) sdp[i][j] = min(sdp[i][j-1],dp[i][j]);}llong ans = sdp[n][n];printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的AtCoder AGC032D Rotation Sort (DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

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