# ZOJ 3623 Battle Ships

Battle Ships Time Limit: 2 Seconds Memory Limit: 65536 KB Battle Ships is a new game which is similar to Star Craft. In this game, the enemy builds a defense tower, which has L longevity. The player has a military factory, which can produce N kinds of battle ships. The factory takes ti seconds to produce the i-th battle ship and this battle ship can make the tower loss li longevity every second when it has been produced. If the longevity of the tower lower than or equal to 0, the player wins. Notice that at each time, the factory can choose only one kind of battle ships to produce or do nothing. And producing more than one battle ships of the same kind is acceptable.

Your job is to find out the minimum time the player should spend to win the game.

Input There are multiple test cases. The first line of each case contains two integers N(1 ≤ N ≤ 30) and L(1 ≤ L ≤ 330), N is the number of the kinds of Battle Ships, L is the longevity of the Defense Tower. Then the following N lines, each line contains two integers t i(1 ≤ t i ≤ 20) and li(1 ≤ li ≤ 330) indicating the produce time and the lethality of the i-th kind Battle Ships.

Output Output one line for each test case. An integer indicating the minimum time the player should spend to win the game.

Sample Input 1 1 1 1 2 10 1 1 2 5 3 100 1 10 3 20 10 100

Sample Output 2 4 5

```#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;
#define mem(a,b) memset((a),(b),sizeof(a));

int dp[350];
struct bat{
int t;
int l;
}a[35];

int main(){
int n,L,mint;
while(cin>>n>>L){
mem(a,0);
mem(dp,0);

for(int i=1;i<=n;i++)
{
cin>>a[i].t>>a[i].l;

}
mint=999999999;
for(int i=0;i<=L;i++)
for(int j=1;j<=n;j++)
{
dp[i+a[j].t]=max(dp[i],dp[i]+a[j].l*(i));
if(dp[i+a[j].t]>=L)
mint=min(mint,i+a[j].t);
}

cout<<mint<<endl;
}

return 0;}```

0 条评论

• ### CodeForces - 140A New Year Table （几何题）当时没想出来-----补题

A. New Year Table time limit per test2 seconds memory limit per test256 megaby...

• ### Codeforces 1291 Round #616 (Div. 2) C. Mind Control（超级详细）

You and your n−1 friends have found an array of integers a1,a2,…,an. You have de...

• ### Codeforces Round #622 (Div. 2) 1313 C1

C1. Skyscrapers (easy version) time limit per test1 second memory limit per te...

• ### 什么是SAP物料主数据里的Batch

Materials are produced and theoretically have the same properties. Nevertheless ...

• ### POJ-1953 World Cup Noise（线性动规）

World Cup Noise Time Limit: 1000MS Memory Limit: 30000K Total Submissio...

• ### How to find “hidden” remote jobs using Google Search.

By using a special search operator with Google search, you can find remote jobs ...

• ### ABAP如何在调试查看EXPORT/IMPORT 内存数据

These memory IDs can be accessed in the debugger, but the option isn't accessibl...

• ### Codeforces 1291 Round #616 (Div. 2) C. Mind Control（超级详细）

You and your n−1 friends have found an array of integers a1,a2,…,an. You have de...

• ### 使用SAP Transaction Launcher将ABAP Webdynpro嵌入到WebClient UI中

THINK twice why you want to include an ABAP webdynpro component into CRM UI, as ...

• ### 使用SAP Transaction Launcher将ABAP Webdynpro嵌入到WebClient UI中

THINK twice why you want to include an ABAP webdynpro component into CRM UI, as ...