刚做的网站关键词就上来了/广告平台网站有哪些

题意：每个人有一个DI值，现在有一个小黑屋，这些人的顺序可以利用这个小黑屋调整，调整方式是入栈出栈方式，也就是说，这里的方案是有卡特兰数个方式。

调整后使得 d1*0 + d2*1 + d3*2 + d4*3 ...... 最小。

 

分析：这个题目竟然会是区间DP。

考虑区间 [ L, R ] ，那么L，可以从任意位置出栈，枚举出栈位置，可以划分为两个部分，也就是说两个子问题，但是如何利用这两个子问题得到 d[L,R]，

d[L,R] = 前一部分 + D[L]*(i-L) + 后一部分 + 后一部分进位。

其中，后一部分的进位是一个前缀和*进多少位。

#include <bits/stdc++.h>using namespace std;const int maxn = 105;
const int inf = 0x3f3f3f3f;int a[maxn];
int d[maxn][maxn];
int su[maxn];int dp(int L,int R) {if(L>=R) return 0;if(d[L][R]!=-1) return d[L][R];d[L][R] = inf;for(int i=L;i<=R;i++) {d[L][R] = min(d[L][R], dp(L+1, i)+(i-L)*a[L]+dp(i+1, R)+(su[R]-su[i])*(i+1-L));}return d[L][R];
}int main()
{//freopen("in.txt","r",stdin);int t;scanf("%d",&t);int kase = 1;while(t--) {int n;scanf("%d",&n);memset(d,-1,sizeof(d));memset(su,0,sizeof(su));for(int i=1;i<=n;i++) {scanf("%d",&a[i]);su[i] = su[i-1] + a[i];     //前缀和
        }printf("Case #%d: %d\n",kase++,dp(1,n));}return 0;
}