HDU 5543 Pick The Sticks（dp) - dblank

# Pick The Sticks

Time Limit: 15000/10000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 841    Accepted Submission(s): 273

Problem Description

The story happened long long ago. One day, Cao Cao made a special order called "Chicken Rib" to his army. No one got his point and all became very panic. However, Cao Cao himself felt very proud of his interesting idea and enjoyed it.

Xiu Yang, one of the cleverest counselors of Cao Cao, understood the command Rather than keep it to himself, he told the point to the whole army. Cao Cao got very angry at his cleverness and would like to punish Xiu Yang. But how can you punish someone because he's clever? By looking at the chicken rib, he finally got a new idea to punish Xiu Yang.

He told Xiu Yang that as his reward of encrypting the special order, he could take as many gold sticks as possible from his desk. But he could only use one stick as the container.

Formally, we can treat the container stick as an L length segment. And the gold sticks as segments too. There were many gold sticks with different length ai and value vi. Xiu Yang needed to put these gold segments onto the container segment. No gold segment was allowed to be overlapped. Luckily, Xiu Yang came up with a good idea. On the two sides of the container, he could make part of the gold sticks outside the container as long as the center of the gravity of each gold stick was still within the container. This could help him get more valuable gold sticks.

As a result, Xiu Yang took too many gold sticks which made Cao Cao much more angry. Cao Cao killed Xiu Yang before he made himself home. So no one knows how many gold sticks Xiu Yang made it in the container.

Can you help solve the mystery by finding out what's the maximum value of the gold sticks Xiu Yang could have taken?

Input
The first line of the input gives the number of test cases, T(1T100). T test cases follow. Each test case start with two integers, N(1N1000) and L(1L2000), represents the number of gold sticks and the length of the container stick. N lines follow. Each line consist of two integers, ai(1ai2000)and vi(1vi109), represents the length and the value of the ith gold stick.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum value of the gold sticks Xiu Yang could have taken.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
ll dp[5000][3], v[1010];
int a[1010], n, l;
int main()
{
int t;
cin>>t;
for(int cas = 1; cas<=t; cas++)
{
scanf("%d%d", &n, &l);
l *= 2;
ll ans = 0;
for(int i = 1; i<=n; i++)
{
scanf("%d%I64d", &a[i], &v[i]);
a[i] *= 2;
ans = max(ans, v[i]);
}
printf("Case #%d: ", cas);
memset(dp, 0, sizeof(dp));
for(int i = 1; i<=n; i++)
for(int j = l; j>=a[i]/2; j--)
for(int k = 0; k<=2; k++)
{
if(j >= a[i])
{
dp[j][k] = max(dp[j][k], dp[j - a[i]][k] + v[i]);
}
if(k && j - a[i]/2 >= 0)
{
dp[j][k] = max(dp[j][k], dp[j-a[i]/2][k-1] + v[i]);
}
}
/* for(int i = 0; i<3; i++)
{
for(int j = 1; j<=l; j++)
printf("%I64d ", dp[j][i]);
printf("\n");
}*/
for(int j = 0; j<=l; j++)
for(int k = 0; k<3; k++)
ans = max(ans, dp[j][k]);
cout<<ans<<endl;
}
return 0;
}

### 相关文章

1. 301 Moved Permanently
301 Moved Permanently>>>

Manueltem 回复
2. Doctor Who is now considered a British Institute and has come a long way since it first aired on November 23rd 1963. The very first show saw the Doctor travel 100,00 years into the past to help some dim cavemen discover light. After 26 seasons and seven Doctors later the series came off our screens in 1989 much to the disappointment of the huge devoted fanbase. In 1996 an attempt was made to revive Doctor Who but it wasnt until June 2005 when it came back with a vengeance with Christopher Eccleston as the ninth Doctor that put the series back on the map as it were. It then went on for 5 years with David Tenant portraying the Doctor until 2010 when Matt Smith took over the role. Today it is still a great family show and has attracted many new fans.

If youre a new or old fan of the show there are Tours and museums you can go and see some of the locations and memorabilia of this classic show. The Doctor Who Tour of London will take you on over 15 locations from the show, some from the new series and some from old sites like the location of The Invasion and Resurrection of the Darleks. The tour also takes you to the TV museum in London where you will get to see some of the cosumes worn in the show and props used. Also you can buy gifts and memorabilia from the shop.

You will learn all about how the shows were made so the tour is also educational. If you want to take pictures of the locations thats not a problem. Remember the front door of 10 Downing Street in Aliens of London? Well you can get up and close to this and get your picture taken in front of the door. Rose Tyler fans will love the tour as you get to drop by her home in the show.

Why not go that extra mile and actually meet a Doctor Who star. Well this is possible with private or group tours. You will get the general tour but included will be a pre-arranged meeting or lunch with a celebrity from the show. This will obviously depend on availability of the celebrity and the cost will reflect the popularity of that celebrity.

There are tours in London and also Wales. The Wales tours take you to Cardiff where you will see lots of location which were featured in shows since 2005. You can leave from London or at Leigh Delamere services station on the M4. There is a Doctor Who exhibition in Cardiff which you get to see. At the end of the Doctor Who tour you get a souvenir group picture sent you by email which is a nice touch.

For seriously devoted Doctor Who fans there is a 3 day tour which takes you to all the locations in both London and Cardiff. You will see locations from the past 45 years as well as recent sites from the lasted Doctor Who series. Day one is based in London where you get to see 15 sites. Day two takes you to Cardiff where you get to mean the real life owner of the to see we have an Gothic property used as the location of the school in Human Nature. The final day is partly spent in Cardiff with a walking tour at Cardiff Bay, then you head back to London but a stop at Stonehenge to see the site of the Pandoica. Then its dinner at The Cloven Hoof pub in Devils End b efore you taken back to central London.

TerryMam 回复
3. Writing a medical thesis or dissertation is a task done by almost all postgraduate and master's medical students. Dissertation is derived from the Latin word disserto which means discuss. It is essential to write successful medical papers such as medicine essays and medical thesis papers. There are several reasons as to why students write medicine essays. One of the reasons is to promote enhancement of critical judgment, research skills as well as analytical skills. Moreover, medicine essay writing produce students with the ability to 4evaluate and analyze data critically.

The initial step for writing medicine essays is to choose a topic. A writer should have at least three topics to choose from. The topic has to be interesting, feasible and relevant. It is essential to write quality medicine essay. Hence, students need to have analytical skills and perfect writing skills. The writing skills will enable them write outstanding essay papers that can be highly regarded by instructors and professors. Teachers often require a lot and expect a lot from their students in terms of medicine essay writing. for this reason, students find essay writing to be an extremely difficult task and hence resort to buying custom medicine essays.

A custom medicine essay has to be written by professional writers who are qualified in the field of nursing. Moreover, the custom medicine essay has to be original and plagiarism free. This means that it has to be written from scratch by experts with many years experience. The many years experience should enable a writer to write any form of medical paper including medical thesis, medicine essay and even medicine research paper. Moreover, experience will enable a writer to write a medicine essay that can guarantee academic success.

Students get custom medicine essays from custom writing company. It is essential to choose the best company so that one can get the best custom medicine essay. The best and the most reliable medicine essay writing company should have some unique characteristics such as affordability and the ability to provide original and superior quality medicine essays. The other quality is that the company has to hire expert writers who can write quality medicine essays and other types of medical papers. The essays should not only be quality but also plagiarism free and free of grammatical and spelling mistakes.

A custom medicine essay has a similar structure to any other academic essay assignment. It has an introduction that introduces the topic and tells the reader what the essay is all about. The second section is the body that has many paragraphs supporting the main topic. Finally there is the conclusion that briefly summarizes what has been discussed in the body section of the essay. Students should choose reliable writing companies so that they can get quality custom papers on several fields such as technology, sociology and law in addition to medicine field.

Our custom writing company is the best company that all clients should rely on when in need of any given type of medicine paper. We provide quality papers that not only plagiarism free but also original. Moreover, our custom papers are affordable and able to guarantee academic excellence at all times. All our medical papers are reliable and sure of satisfying clients at all times.

Felixblity 回复
4. A Biological Masterpiece, But Subject to Many Ills
The human foot is a biological masterpiece. Its strong, flexible, and functional design enables it to do its job well and without complaint—if you take care of it and don't take it for granted.
healthThe foot can be compared to a finely tuned race car, or a space shuttle, vehicles whose function dictates their design and structure. And like them, the human foot is complex, containing within its relatively small size 26 bones (the two feet contain a quarter of all the bones in the body), 33 joints, and a network of more than 100 tendons, muscles, and ligaments, to say nothing of blood vessels and nerves.
https://www.cialissansordonnancefr24.com/cialis-livraison-24h/

Jessiediary 回复