HDU 4283 You Are the One(区间dp）

题意:给你T组数据，在一个舞会上有n个人，每个人有个不开心值ai值，他第K个上场，则不开心的值为（k-1）*ai。假设原计划每个人按照序号上场，但现在有一间类似栈的小黑屋可以改变大家的出场顺序,计算出最小的不开心值。

题解：现在有一个i, i + 1,i+2,i+3,i+4的区间，假设i号第K个上场，则[i+1, i+k-1]这个区间在i号之前上场，[i+k,i+4]这个区间会在i号后面上场，所以枚举i号上场的顺序找出最小值就可以了，状态转移方程为min(dp[i][j],val[i] * (k-1) + (sum[j] - sum[i+k]) * k + dp[i+1][i+k-1] + dp[i+k,i+4])ps:在初始化上，对于i<=j要初始化为0，因为状态转移方程会出现i > j的情况。

#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <queue> #include <stack> #include <list> #include <map> #include <set> #define LL long long #define INF 0x3f3f3f3f #define MAX 2200 #define MEM(n,v) memset(n, 0, sizeof(n)) #define Min(n,m) n < m ? n : m #define Max(n,m) n > m ? n : m #define Forup(x,y) for(int i = x; i < y; i++) #define Fordown(x,y) for(int i = x; i > y;i--) int dp[MAX][MAX], sum[MAX], t, n,num[MAX]; using namespace std; void get_dp() { /*memset(dp, INF, sizeof(dp)); Forup(1, n + 1) dp[i][i] = 0;*/ MEM(dp,0); for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) dp[i][j] = INF; for (int l = 1; l < n; l++) for (int i = 1; i < n; i++) { int j = i + l; if (j <= n) for (int k = i; k <= j; k++) dp[i][j] = Min(dp[i][j], (sum[j] - sum[k])*(k - i + 1) + num[i] * (k - i) +dp[i + 1][k] + dp[k + 1][j]); } } int main() { scanf("%d", &t); Forup(1, t + 1) { scanf("%d", &n); MEM(sum,0); Forup(1, n + 1) { scanf("%d", &num[i]); sum[i] = sum[i-1] + num[i]; } get_dp(); //printf("%d\n", dp[1][n]); printf("Case #%d: %d\n", i, dp[1][n]); } return 0; }