题目概述
你是一个公司的员工,你会按时间顺序受到一些产品的订单,你需要用一个栈来改变这些订单的顺序(每个产品都必须入栈和出栈一次)。
按初始顺序,每次可以将一个产品入栈,或将栈顶产品弹至现在的序列末尾。
每个产品有一个制作时间t i 和单位时间惩罚值d i 。
总的惩罚值为∑ ni=1 (s i × d i ),其中s i 为第i个产品的完成时间,你需要最小化总的惩罚值。
分析
考虑区间 \(dp\)。
设 \(f_{i,j}\) 表示处理 \([i,j]\) 最小的总惩罚值。
分类：
- 产品 \(i\) 第一个出栈，则有 \(f_{i,j}=t_i\times sd_{i,j}+f_{i+1,j}\)
- 产品 \(i\) 第 \(k\) 个出栈，则有 \(f_{i,j}=f_{i+1,k}+f_{k + 1,j}+st_{i,k}\times(d_i+sd_{k+1,j})\)。
第二种情况第 \(k\) 个出栈，那肯定 \(i+1\) 到 \(k\) 都已经出完栈了，所以后这些贡献。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t[205],d[205];
int st[205][205],sd[205][205],f[205][205];
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>t[i]>>d[i];for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){st[i][j]=st[i][j-1]+t[j];sd[i][j]=sd[i][j-1]+d[j];}}for(int i=n;i>=1;i--){f[i][i]=t[i]*d[i];for(int j=i+1;j<=n;j++){f[i][j]=t[i]*sd[i][j]+f[i+1][j];for(int k=i+1;k<=j;k++){f[i][j]=min(f[i][j],f[i+1][k]+st[i][k]*(d[i]+sd[k+1][j])+f[k+1][j]);}}}cout<<f[1][n];
}