本文共 3174 字,大约阅读时间需要 10 分钟。
1、
2、题目大意:
有n个男孩,现在要一个一个的登台,每个男孩都有一个diaosi值,如果他是第k个登台的,他的最终的diaosi值就等于他的diaosi值*(k-1),他前边等待了K-1个人,现在要确定一个登台顺序 ,使得所有男孩的diaosi值最小
3、思路分析
设状态dp[i][j]表示i-j区间内i是第k个登台的
dp[s][e]=min(dp[s][e],dp[s+1][e]+a[s]*(e-s));//s是最后一个选出来的 dp[s][e]=min(dp[s][e],dp[s+1][e]+Delay(s,e));//第一个被选出来 for(int k=s+1;k<=e;k++) { dp[s][e]=min(dp[s][e],dp[s+1][k]+dp[k+1][e]+a[s]*(k-s)+Delay(k,e)*(k-s+1)); //最后是k-s+1,k后边的人还要等k }
4、题目:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1351 Accepted Submission(s): 637
2 512345554322
Case #1: 20Case #2: 24
5、AC代码:
#include#include #include using namespace std;#define N 105#define INF 1<<29int a[N],sum[N];int dp[N][N];//dp[i][j]表示i是第k个被选出来的int Delay(int s,int e){ if(s>e) return 0; return sum[e]-sum[s];}void DP(int n){ for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) dp[i][j]=INF; } for(int i=0;i<=n;i++) { dp[i][i]=0; } for(int d=1;d<=n;d++) { for(int i=1;i+d-1<=n;i++) { int s=i; int e=i+d-1; //int delay=Delay(s,e); dp[s][e]=min(dp[s][e],dp[s+1][e]+a[s]*(e-s));//s是最后一个选出来的 dp[s][e]=min(dp[s][e],dp[s+1][e]+Delay(s,e));//第一个被选出来 for(int k=s+1;k<=e;k++) { dp[s][e]=min(dp[s][e],dp[s+1][k]+dp[k+1][e]+a[s]*(k-s)+Delay(k,e)*(k-s+1)); //最后是k-s+1,k后边的人还要等k } } }}int main(){ int t,n,cas=0; scanf("%d",&t); while(t--) { cas++; scanf("%d",&n); sum[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } DP(n); printf("Case #%d: %d\n",cas,dp[1][n]); } return 0;}/*2051 2 3 4 555 4 3 2 261 1 1 1 1 177 7 7 7 7 7 7*/
转载地址:http://awcdi.baihongyu.com/