首页 > 代码库 > hdu_4283_You Are the One(区间DP)
hdu_4283_You Are the One(区间DP)
题目链接：hdu_4283_You Are the One
题意：
有n个人，每个人有个屌丝值，如果果他是第K个上场，不开心指数就为(K-1)*D，然后有个小黑屋，可以调整他们的出场顺序，现在让你调整顺序，使不开心指数最小
题解：
考虑区间DP，dp[i][j]表示第i个人到第j个人这个区间的不开心指数最小的方案，然后我们更新dp[i][j]，考虑第i个人在这个区间中第k出场，
那么dp[i][j]=min(dp[i][j],v[i]*(k-i)+(k-i+1)*(sum[j]-sum[k])+dp[i+1][k]+dp[k+1][j]),其中dp[i+1][k]表示将第i个人调到这个区间的第k出场，那么后i+1到k的最优出场顺序就是dp[i+1][k]，把第i个人调到k出场后，后k+1到j的人的最优出顺序为dp[k+1][j]，因为把第i个人向后调了k-i，所以不开心指数会加v[i]*(k-i),
因为后面k+1到j的人排在了(k-i+1)个人的后面，所有这个区间的人的不开心指数全部要加上去，即：(k-i+1)*(sum[j]-sum[k])
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 5 inline void up(int &a,int b){if(a>b)a=b;} 6 7 int t,n,ic=1,dp[105][105],sum[105],v[105],inf=1e9+7; 8 9 int main()10 {11 scanf("%d",&t);12 while(t--)13 {14 scanf("%d",&n);15 F(i,1,n)scanf("%d",v+i),sum[i]=sum[i-1]+v[i];16 memset(dp,0,sizeof(dp));17 F(i,1,n)F(j,i+1,n)dp[i][j]=inf;18 F(l,1,n-1)F(i,1,n-l)F(k,i,i+l)19 up(dp[i][i+l],v[i]*(k-i)+(k-i+1)*(sum[i+l]-sum[k])+dp[i+1][k]+dp[k+1][i+l]);20 printf("Case #%d: %d\n",ic++,dp[1][n]);21 }22 return 0;23 }
hdu_4283_You Are the One(区间DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。