You Are the One HDU - 4283

Link: You Are the One HDU - 4283

Description

点击查看题面

　　The TV shows such as You Are the One has been very popular. In order to meet the need of boys who are still single, TJUT hold the show itself. The show is hold in the Small hall, so it attract a lot of boys and girls. Now there are n boys enrolling in. At the beginning, the n boys stand in a row and go to the stage one by one. However, the director suddenly knows that very boy has a value of diaosi D, if the boy is k-th one go to the stage, the unhappiness of him will be (k-1)*D, because he has to wait for (k-1) people. Luckily, there is a dark room in the Small hall, so the director can put the boy into the dark room temporarily and let the boys behind his go to stage before him. For the dark room is very narrow, the boy who first get into dark room has to leave last. The director wants to change the order of boys by the dark room, so the summary of unhappiness will be least. Can you help him?

输入描述:

　　The first line contains a single integer T, the number of test cases. For each case, the first line is n (0 < n <= 100)
　　The next n line are n integer D1-Dn means the value of diaosi of boys (0 <= Di <= 100)

输出描述:

　　For each test case, output the least summary of unhappiness .

Sample Input
2
　　
5
1
2
3
4
5

5
5
4
3
2
2

Sample Output
Case #1: 20
Case #2: 24

Probelm solving

这道题的意思简单来说就是给你一个序列，序列中你可以按照本来顺序选择数，每次选一个数的花费为，为选择的次数，为被选择的数的值。但是你也可以将现在按照顺序来的数放到一个栈里面，想要取出来的时候再取出来。

区间dp专题里面的题，就不往别的方向思考了（然而我还是想了贪心虽然没过233

我们令表示这个区间内的数全部挑选完时的最小花费。然后我们让这个区间内的第个数在第次被选择，也就是说这个区间被我们分成了三部分，区间内的数是第次被选择的，区间内的数是选了之后被选择的，所以我们可以得到一个转移方程，

dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+dp[i+k][j]+(k-1)*a[i]+k*(sum[j]-sum[i+k-1]))

其中

  • 为上面分析的三个区间中两个区间的最小花费
  • 表示的是第个数被取走的花费
  • 表示的是选择了之后剩下的所有数在原来最小的基础上要多花费的部分。

然后我们枚举每次更新最小值即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
const ll maxn = 105;
const ll mod = 1e9+7;
const ll INF = 0x3f3f3f3f;
ll d[4][2]={1,0,0,1,-1,0,0,-1};
ll dp[maxn][maxn],a[maxn],sum[maxn];
int main() {
    ios::sync_with_stdio(0);
    #ifdef Uncle_drew
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #else
    #endif
    ll t,n,cas=0;
    cin>>t;
    while(t--){
        cas++;
        cin>>n;
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        for(ll i=1;i<=n;i++){
            for(ll j=i+1;j<=n;j++){
                dp[i][j]=INF;
            }
        }
        for(ll i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
        for(ll l=2;l<=n;l++){
            for(ll i=1;i+l<=n+1;i++){
                ll j=i+l-1;
                for(ll k=1;k<=j-i+1;k++){
                    dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+dp[i+k][j]+(k-1)*a[i]+k*(sum[j]-sum[i+k-1]));
                }
            }
        }
        cout<<"Case #"<<cas<<": "<<dp[1][n]<<endl;
    }
    return 0;
}
赏