CF19B Checkout Assistant(01背包变形)

时间：2023-12-12 22:37:02 cj19b电容器接触器

题意翻译

题目描述

Bob 来到现购自运商店，会nn把货物放进他的手推车里，然后到收银台付款。每件商品的价格由它的价格决定c_ici与收银员一起扫描时间t_iti秒定义。

收银员在扫描商品时，Bob 一些其他商品可以从他的手推车里偷走。Bob 需要恰好11偷一件商品几秒钟。Bob 最少要付给收银员的钱是多少？请记住，收银员扫描商品的顺序是由 Bob 决定。

输入格式

输入第一行包含数nn（1 \le n \le 20001≤n≤2000）。接下来nn每行每件商品都是一对数t_iti，c_ici（0 \le t_i \le 20000≤ti≤2000，1 \le c_i \le 10^91≤ci≤109）描述。如果t_iti是当收银员扫描商品时ii时，Bob 什么都不能偷。

输出格式

输出一个数字—— Bob 最小金额是多少？

#include  #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  typedef long long ll; typedef unsigned long long ull; using namespace std; const int MN = 65005; const int MAXN = 1000005; const int INF = 0x3f3f3f3f; #define reg register #define IOS ios::sync_with_stdio(false)  int n; int t[2005]; int c[2005]; ll ans = 2e12; ll dp[4005];  int main() {  scanf("%d", &n);  for (int i = 1; i <= n; i  ) {   scanf("%d %d", t   i, c   i);   t[i] = min(n, t[i]   1);  }  for (int i = 1; i <= n   n; i  ) {   dp[i] = 1e18;  }  for (int i = 1; i <= n; i  ) {   for (int j = n   n; j >= t[i]; j--) {    dp[j] = min(dp[j], dp[j - t[i]]   c[i]);   }  }  for (int i = n   n; i >= n; i--) {   ans = min(ans, dp[i]);  }  printf("%lld\n", ans);  return 0; }

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

CF19B Checkout Assistant(01背包变形)

题意翻译

题目描述

输入格式

输出格式

相关文章