题意翻译
题目描述
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 <iostream> #include <cstdio> #include <string> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <cstring> #include <set> #include <cmath> #include <map> 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; }