大意： 有一个队列，每个人有一个愤怒值D，如果他是第K个上场，不开心指数就为(K-1)*D。但是边上有一个小黑屋，可以一定程度上调整上场程序，求最小的愤怒值之和
思路： dp[i][j]表示i->j这个区间的最优解，也就是最小值，考虑第i个人，他一共有j - i + 1中上场方式，可以第一个，第二个...第j - i + 1个，所以枚举这个上场方式，那么dp[i][j] = min(dp[i][j], dp[i + 1][i + k - 1] + (k - 1) * a[i] + dp[i + k][j] + k * (sum[j] - sum[i + k - 1])), 这里的k代表i是第几个上场的，假设i是第k个上场的，那么i上场之前有k-1个人，所以要加上dp[i + 1][i +k - 1]，第i个人的愤怒值为(k - 1) * a[i], 那么剩下的人就是k之后上场的，所以dp[i + k][j] + k * (sum[j] - sum[i +k - 1]), 还有他们所有的愤怒值都要加起来，所以就是(sum[j] - sum[i + k - 1]) * k;
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn = 110; const int inf = (1 << 25); int a[maxn], sum[maxn], dp[maxn][maxn]; int main() { int T, n, kase = 0; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[i] = sum[i - 1] + a[i]; } memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) dp[i][j] = inf; for (int i = n; i >= 1; i--) { for (int j = i; j <= n; j++) { for (int k = 1; k <= j - i + 1; k++) dp[i][j] = min(dp[i][j], dp[i + 1][i + k - 1] + (k - 1) * a[i] + dp[i + k][j] + (sum[j] - sum[i + k - 1]) * k); } } printf("Case #%d: %d ", ++kase, dp[1][n]); } return 0; }