S2553 产品排序

admin

【问题描述】

你是一个公司的员工，你会按时间顺序受到一些产品的订单，你需要用一个栈来改变这些订单的顺序（每个产品都必须入栈和出栈一次）。

按初始顺序，每次可以将一个产品入栈，或将栈顶产品弹至现在的序列末尾。每个产品有一个制作时间ti和单位时间惩罚值di，总的惩罚值为∑siXdi ，其中si为第 个产品的完成时间，你需要最小化总的惩罚值。

【输入】

输入文件product.in。

第一行一个数 ，表示产品个数。

接下来n行，每行两个数表示ti和di 。

【输出】

输出文件product.out。一行一个数表示最小的总惩罚值。

【输入输出样例】

product.in	product.out
4 1 4   3 2 5 2 2 1	40

【样例解释】

操作步骤	排序后的序列(数字表示产品编号)
1.将第一个产品入栈
2.弹出栈顶元素	1
3.将第二个产品入栈	1
4.弹出栈顶元素	1 2
5.将第三个产品入栈	1 2
6.将第四个产品入栈	1 2
7.弹出栈顶元素	1 2 4
8.弹出栈顶元素	1 2 4 3

总惩罚值为1*4+(1+3)*2+(1+3+2)*1+(1+3+2+5)*2=40

admin

(2015年北大自招夏令营)
考虑最后出栈的是i，则1至i-1在i入栈前就已经弹出，与i+1至n的顺序没有关系，并且i+1至n的惩罚值只跟他们的顺序与∑tj(1<=j<i)有关即可以将[1,n]的计算转化为两个子问题[1,i-1]和[i+1,n]。
令f(l,r)表示[l,r]的最小惩罚值。
f(l,r)= min(f(l,m-1)+f(m+1,r)+(stm-1-stl-1)*(sdr-sdm)+(str-stl-1)*dm) (l<=m<=r,其中st为时间前缀和，sd为惩罚前缀和)
时间复杂度O(N3)。空间复杂度O(N2)。

1. #include<iostream>
   
2. #include<cstdio>
   
3. #define FOR(i,a,b) for(int i=a;i<=b;i++)
   
4. using namespace std;
   
5. typedef long long ll;
   
6. const int N=550;
   
7. const ll INF=1e13;
   
8. int n;
   
9. ll t[N],d[N],st[N],sd[N],f[N][N];
   
10. int main()
    
11. {
    
12.         freopen("product.in","r",stdin);
    
13.         freopen("product.out","w",stdout);
    
14.         scanf("%d",&n);
    
15.         FOR(i,1,n) scanf("%lld%lld",&t[i],&d[i]);
    
16.         FOR(i,1,n) st[i]=st[i-1]+t[i],sd[i]=sd[i-1]+d[i];
    
17.         FOR(i,1,n) f[i][i]=t[i]*d[i];
    
18.         FOR(L,2,n)
    
19.         {
    
20.                 FOR(i,1,n-L+1)
    
21.                 {
    
22.                         int j=i+L-1;
    
23.                         f[i][j]=INF;
    
24.                         FOR(k,i,j-1)
    
25.                         f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+(st[k]-st[i-1])*(sd[j]-sd[k]));
    
26.                         f[i][j]=min(f[i][j],f[i+1][j]+d[i]*(st[j]-st[i-1]));
    
27.                         //cout<<i<<' '<<j<<' '<<f[i][j]<<endl;
    
28.                 }
    
29.         }
    
30.         printf("%lld",f[1][n]);
    
31. }

复制代码

admin

【数据说明】
30%:n≤15
50%:n≤100
100%:n≤200,t_i,d_i≤1000