当前位置: 首页 > news >正文

产品排序

题目概述

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

按初始顺序,每次可以将一个产品入栈,或将栈顶产品弹至现在的序列末尾。

  每个产品有一个制作时间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];
}
http://www.hskmm.com/?act=detail&tid=21058

相关文章:

  • 环形链表II-leetcode
  • ubuntu20.04安装nvidia显卡
  • [线段树系列 #6] 标记永久化
  • 9.29
  • c语言switch和if语句
  • Qt(制作一个方便的文本编辑器)
  • Java EE初阶启程记05---线程安全 - 指南
  • DataGridView表格控件使用说明
  • 题解:P7126 [Ynoi2008] rdCcot
  • 个人微信机器人开发api接口
  • MyBatis技术详解:从入门到高效开发 - 详解
  • 解码数据结构队列
  • 解决升级 Windows 11 24H2 后 NAS 共享无法显示的问题
  • 【还未找到原题】宝石(GEM) - Harvey
  • 第八篇
  • C# AStar 算法 - 实际应用
  • nocobase 源码安装
  • 航司网站url后缀参数FECU分析
  • 子网掩码完全指南:从入门到精通
  • 微信群机器人API
  • 9月29号
  • 【CF19E】Fairy - Harvey
  • Python从入门到实战 (14):工具落地:用 PyInstaller 打包 Python 脚本为可执行文件 - 实践
  • Harmony实现流转开发之音乐播放器跨设备流转 - 实践
  • 软件工程中线性回归应用
  • 解决秒杀高并发的一些方案
  • 构建移动网关:Air780EPM用4G为WiFi和LAN设备供网
  • 9.29模拟赛总结
  • 多corner综合
  • 优化 if/else 的四种设计模式