专栏首页CSDN旧文ZOJ 3623 Battle Ships

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...

    风骨散人Chiam
  • 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...

    风骨散人Chiam
  • Codeforces Round #622 (Div. 2) 1313 C1

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

    风骨散人Chiam
  • 什么是SAP物料主数据里的Batch

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

    Jerry Wang
  • POJ-1953 World Cup Noise(线性动规)

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

    ShenduCC
  • 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...

    matinal
  • 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...

    风骨散人Chiam
  • 使用SAP Transaction Launcher将ABAP Webdynpro嵌入到WebClient UI中

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

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

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

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券