有N个人要出场，每个人有个不爽的值，如果他第i个出场 那么 他的愤怒值为 num[i]*(i-1)，求怎么样排出场顺序，能使得总得愤怒值最小
dp[i][j] 当然表示第i个人 到第j个人这个区间的最小愤怒值，这里要注意的是 只对这个区间进行考虑， 比如 dp[2][5],只需要考虑2到5号人的出场安排，此区间前面的不需要去考虑
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; int dp[1000 + 5][1000 + 5]; int num[1000 + 5]; int sum[1000 + 5]; int n; void clear() { memset(num,0,sizeof(num)); memset(sum,0,sizeof(sum)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dp[i][j] = inf; } int main() { int t; int Case = 0; scanf(%d,&t); while(t--) { scanf(%d,&n); clear(); for(int i=1;i<=n;i++) { scanf(%d,&num[i]); sum[i] = sum[i-1] + num[i]; } for(int k=1;k<=n;k++) { for(int i=1;i<=n-k;i++) { int j = i + k; for(int p=1;p<=j-i+1;p++) dp[i][j] = min(dp[i][j],dp[i+1][i+p-1]+dp[i+p][j] + (p-1)*num[i] + (sum[j]-sum[i+p-1])*p); } } printf(Case #%d: %d ,++Case,dp[1][n]); } return EXIT_SUCCESS; }