CodeForces 19B Checkout Assistant

B. Checkout Assistant

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Bob came to a cash & carry store, put n items into his trolley, and went to the checkout counter to pay. Each item is described by its priceci and time ti in seconds that a checkout assistant spends on this item. While the checkout assistant is occupied with some item, Bob can steal some other items from his trolley. To steal one item Bob needs exactly 1 second. What is the minimum amount of money that Bob will have to pay to the checkout assistant? Remember, please, that it is Bob, who determines the order of items for the checkout assistant.

Input

The first input line contains number n (1 ≤ n ≤ 2000). In each of the following n lines each item is described by a pair of numbers tici(0 ≤ ti ≤ 2000, 1 ≤ ci ≤ 109). If ti is 0, Bob won't be able to steal anything, while the checkout assistant is occupied with item i.

Output

Output one number — answer to the problem: what is the minimum amount of money that Bob will have to pay.

Examples

input

4
2 10
0 20
1 5
1 3

output

8

input

3
0 1
0 10
0 100

output

111
简单01背包,每个物品的付钱时间可以当作是买了这个物品还可以送你多少个物品。物品的数量相当于背包的体积,物品的价值相当于价值,问题就变成求背包体积大于等于n时,可以得到的最小价值
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
const long long int MAX=(long long int)1<<62;
long long int dp[2005];
long long int a[2005][2];
int n;
int main()
{
   scanf("%d",&n);
   for(int i=1;i<=n;i++)
      scanf("%lld%lld",&a[i][0],&a[i][1]),a[i][0]++;
   for(int i=0;i<=n;i++)
	   dp[i]=MAX;
   dp[0]=0;
   for(int i=1;i<=n;i++)
   {
	   for(int j=n;j>=0;j--)
	   {
		   if(j>=a[i][0])
		   {
			   dp[j]=min(dp[j],dp[j-a[i][0]]+a[i][1]);
		   }
		   else
			   dp[j]=min(dp[j],a[i][1]);
	   }
   }
   printf("%lld\n",dp[n]);
   return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

关关的刷题日记05 —— Leetcode 217. Contains Duplicate 方法1和方法2

题目 Leetcode 217. Contains Duplicate Given an array of integers, find if the arra...

34670
来自专栏微信公众号:Java团长

谈谈我对面向对象以及类与对象的理解

对于刚接触JAVA或者其他面向对象编程语言的朋友们来说,可能一开始都很难理解面向对象的概念以及类和对象的关系。笔者曾经带过一个短期培训班教授java入门基础,在...

12120
来自专栏前端儿

苹果

ctest有n个苹果,要将它放入容量为v的背包。给出第i个苹果的大小和价钱,求出能放入背包的苹果的总价钱最大值。

10920
来自专栏灯塔大数据

干货 | 国外大神总结的10个Java编程技巧!

“任何可能出错的事情,最后都会出错。”这就是人们为什么喜欢进行“防错性程序设计”的原因。

13310
来自专栏iKcamp

翻译连载 |《你不知道的JS》姊妹篇 |《JavaScript 轻量级函数式编程》- 第 6 章:值的不可变性

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 第 6 章:值的不可变性 在第 ...

22650
来自专栏Albert陈凯

影响Scala语言设计的因素列表

Scala语言设计概述 Scala的设计受许多编程语言和研究思想的影响。事实上,仅很少的Scala的特点是全新的;大多数都已经被以另外的形式用在其他语言中了。...

36870
来自专栏计算机视觉与深度学习基础

POJ1837

好巧妙的背包 杠杆原理:力臂=力距*力 当平衡时,左右的力臂相同,可以把左边的作为负的,右边的作为正的。 dp[i][j]表示用前i个钩码挂出力臂和为j的情况的...

20990
来自专栏后端技术探索

常见算法面试题

这几天在网上看到一篇关于算法面试题的博客,归纳的很好,有不少经典的题目,大部分来自《编程珠玑》、《编程之美》、《代码之美》三本书。这里给出书上的解答以及一些思考...

38320
来自专栏刘笑江的专栏

SCIP学习笔记

35240
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第8章 函数式编程(FP)(1)第8章 函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

13220

扫码关注云+社区

领取腾讯云代金券