XMU1460 最高得分 &&124 - ZOJ Monthly, March 2013 - D 01背包巧妙处理

The ancient civilization, such as Old Babylonianhas, Ancient Egypt and etc, some features in common. One of them is the tomb because of the influence of the religion. At that time, the symbol of the tomb is the pyramid. Many of these structures featured a top platform upon which a smaller dedicatory building was constructed, associated with a particularMaya deity. Maya pyramid-like structures were also erected to serve as a place of interment for powerful rulers.

Now there are N coffin chambers in the pyramid waiting for building and the ruler has recruited some workers to work forT days. It takes ti days to complete the ith coffin chamber. The size of theith coffin chamber is si. They use a very special method to calculate the reward for workers. If starting to build theith coffin chamber when there are t days left, they can gett*si units of gold. If they have finished a coffin chamber, then they can choose another coffin chamber to build (if they decide to build theith coffin chamber at the time t, then they can decide next coffin chamber at the timet-ti).

At the beginning, there are T days left. If they start the last work at the timet and the finishing time t-ti < 0, they will not get the last pay.

Input

There are few test cases.

The first line contains N, T (1 ≤ N ≤ 3000,1 ≤T ≤ 10000), indicating there are N coffin chambers to be built, and there areT days for workers working. Next N lines contains ti,si (1 ≤ ti, si ≤ 500).

All numbers are integers and the answer will not exceed 2^31-1.

Output

For each test case, output an integer in a single line indicating the maxminal units of gold the workers will get.

Sample Input

3 103 41 22 1

Sample Output

62

Hint

Start the second task at the time 10
Start the first task at the time 9
Start the third task at the time 6
The answer is 10*2+9*4+6*1=62

http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=4962

题意：

3 103 41 22 1

输入 n m n个题目 ，总的时间m

每个题目的 a b a表示做这道题需要的时间 4是做这道题的单位得分（总得分为单位得分乘以做这道题的时候的剩余时间） 没道题都确信能够做出切一次性ac 问能得到的最高分

注意本题是开始做的时候就给分

第 10秒开始做第二道哦题目 得到10*2分
第9秒的时候做第一道得到9*4、

第6秒的时候做第三道得到6*1分

一共得到
The answer is 10*2+9*4+6*1=62

思路和上面的差不多 做了下小修改

#include <stdio.h>#include <string.h>#include <math.h>#include <algorithm>using namespace std;struct st{int w;double v;}a[3111];double dp[11111];bool cmp(st a,st b){if(fabs((a.v/a.w-b.v/b.w))<0.0000001)  //if(a.v/a.w==b.v/b.w)return a.w>b.w;elsereturn a.v/a.w>b.v/b.w;}int main(){int i,j,m,n;int t;double max=0;while(scanf("%d%d",&n,&t)!=EOF){max=0;for(i=0;i<n;i++){scanf("%d%lf",&a[i].w,&a[i].v);}memset(dp,0,sizeof(dp));sort(a,a+n,cmp);for(i=0;i<n;i++){for(j=(int)t;j>=a[i].w;j--){if(dp[j]<dp[j-a[i].w]+a[i].v*(t-j+a[i].w))  dp[j]=dp[j-a[i].w]+a[i].v*(t-j+a[i].w);if(dp[j]>max)max=dp[j];}}//for(i=0;i<=t;i++)//printf("%lf ",dp[i]);printf("%.0lf\n",max);}return 0;}