You Are The One

題意：有n個人準備按順序上臺，上臺前有個小黑屋（先進后出，即棧），可以被安排進去等待，也可以直接上臺，一個人一旦被安排進去，后面的人就可以先上臺（小黑屋無限大）。每個人有一個憤怒值angry，如果他是第k個上臺的，那么他的怒氣和就是(k-1)*angry，如何運用小黑屋安排上臺順序，使得這n個人的怒氣總和最小。

思路：這是一道區間dp題（這幾天做的都是區間dp的專題，不是就見鬼了），狀態很容易想到，用f[l][r]，表示l~r這r-l+1個人的最小怒氣總和，那么如何轉移，其實區間dp大概的套路也就是三個for( for len ; for l,r ; for k (l,r) )，而這題其中的小細節也比較容易觀察到，那么問題來了，這也是為什么這題區間dp拿來寫的原因，一般的k枚舉都是l到r來劃分區間，但是這題顯然沒有什么用，為什么沒用？因為要用小黑屋啊！如果直接枚舉斷點，而這題的l, r點是沒什么關系的（如果真的有，個人感覺也很難推出，因為每個人的出場順序其實是不一定的），怎么算出最優？（不用小黑屋也可以看做進去馬上出來，問題不大），那么考慮到一個問題，既然出場順序不一定，那k就枚舉出場順序吧，顯然區間l~r的一個人出場順序就只有r-l+1種，因為如果只有len個人，怎么做到第len+1出場？（一場跑步比賽，你超越了最后一名，你是第幾！），至此，轉移的for考慮完了，那么這個k來枚舉誰呢？第一個？最后一個？隨便一個？其實，隨便一個都可以，因為最后區間最優，其實順序是定的，所以先枚舉誰都可以，那么就枚舉這個區間的第一個吧，因為好寫。可以想想，第一個人第k個出場，是不是1~1+k-1比他早出場，1+k~end在他后面出場（所以這些人都多等待了k個人，因而怒氣值要多加上k次），那么轉移式子就出來了。
題外：寫這題的契機其實有二，一是昨天聽同學說了一題區間dp挺有意思的去補了一發，發現自己竟然寫出來了dp，說出來是有點開心的，雖然那題并不復雜。而之前一直很害怕dp，覺得能想出來轉移的（當然是要能A的正解，瞎想的沒有意義）簡直就是神仙。最近真的認真思考了一些dp題，發現從簡入繁，其實dp挺有意思的，而且個人感覺做dp最大的收益就是很容易看懂別人寫的代碼（不只是dp的），因為其實dp挺鍛煉思維的，一旦開始思考了，理解能力肯定不斷地提升。二就是覺得這題區間dp的for套路有意思，k是來枚舉順序的，和別的區間dp（目前自己做到的）不太一樣，就放了上來。

---

Codes：

#include <bits/stdc++.h> #define pb push_back #define de(x) cout << #x << " = " << x << endl #define clr(a,b) memset(a,b,sizeof(a)) using namespace std;typedef long long ll; const int INF = 0x3f3f3f3f; const int N = 110;int f[N][N]; int a[N], pr[N];int main() {int n;int cas = 1;int t;scanf("%d", &t);while ( t -- ){scanf("%d", &n);pr[0] = 0;for ( int i = 1; i <= n; i ++ ){scanf("%d", &a[i]);pr[i] = pr[i-1] + a[i];f[i][i] = 0;}for ( int len = 2; len <= n; len ++ ){for ( int l = 1, r; ( r = l + len - 1 ) <= n; l ++ ){f[l][r] = INF;for ( int k = 1; k <= len; k ++ ){f[l][r] = min( f[l][r], (k-1)*a[l] + f[l+1][l+k-1] + f[l+k][r] + k*(pr[r]-pr[l+k-1]) );}}}printf("Case #%d: %d\n", cas++, f[1][n]); }return 0; }

轉載于:https://www.cnblogs.com/FormerAutumn/p/9819741.html

總結

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

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