华师一附中OI组

标题: S2553 产品排序 [打印本页]

作者: admin 时间: 2021-10-14 14:49
标题: S2553 产品排序

【问题描述】

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

按初始顺序，每次可以将一个产品入栈，或将栈顶产品弹至现在的序列末尾。每个产品有一个制作时间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 时间: 2021-10-14 14:50
【数据说明】
30%:n≤15
50%:n≤100
100%:n≤200,t_i,d_i≤1000

作者: admin 时间: 2021-10-14 14:51
(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)。

#include<iostream>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=550;
const ll INF=1e13;
int n;
ll t[N],d[N],st[N],sd[N],f[N][N];
int main()
{
freopen("product.in","r",stdin);
freopen("product.out","w",stdout);
scanf("%d",&n);
FOR(i,1,n) scanf("%lld%lld",&t[i],&d[i]);
FOR(i,1,n) st[i]=st[i-1]+t[i],sd[i]=sd[i-1]+d[i];
FOR(i,1,n) f[i][i]=t[i]*d[i];
FOR(L,2,n)
{
FOR(i,1,n-L+1)
{
int j=i+L-1;
f[i][j]=INF;
FOR(k,i,j-1)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+(st[k]-st[i-1])*(sd[j]-sd[k]));
f[i][j]=min(f[i][j],f[i+1][j]+d[i]*(st[j]-st[i-1]));
//cout<<i<<' '<<j<<' '<<f[i][j]<<endl;
}
}
printf("%lld",f[1][n]);
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)