DiggingTime Limit:2 Seconds Memory Limit:65536 KB
When it comes to theMaya Civilization, we can quickly remind of a term called the end of the world. It’s not difficult to understand why we choose to believe the prophecy (or we just assume it is true to entertain ourselves) if you know the other prophecies appeared in theMaya Calendar. For instance, it has accurately predicted a solar eclipse on July 22, 2009.
The ancient civilization, such asOld Babylonianhas,Ancient Egyptand 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 areNcoffin chambers in the pyramid waiting for building and the ruler has recruited some workers to work forTdays. It takestidays to complete theithcoffin chamber. The size of theithcoffin chamber issi. They use a very special method to calculate the reward for workers. If starting to build theithcoffin chamber when there aretdaysleft, they can gett*siunits of gold. If they have finished a coffin chamber, then they can choose another coffin chamber to build (if they decide to build theithcoffin chamber at the timet, then they can decide next coffin chamber at the timet-ti).
At the beginning, there areTdays left. If they start the last work at the timetand the finishing timet-ti < 0, they will not get the last pay.
Input
There are few test cases.
The first line containsN,T(1 ≤N≤ 3000,1 ≤T≤ 10000), indicating there areNcoffin chambers to be built, and there areTdays for workers working. NextNlines containsti,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 Input3 103 41 22 1Sample Output62Hint
题意：n个任务，剩余t的时间，完成每个任务会消耗时间ti，同时也会得到t*si的价值，求怎么安排任务得到的价值最大
题解：一开始只想用背包，出不来样例。排个序后就可以了。至于为什么，我也不知道，，（看来还是没参透dp的精髓。。），想来大概是背包得先背性价比高的来保证贪心的思想吧。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long longusing namespace std;const int M=10010;const int N=3030;int n,T;ll dp[M];struct node {int t,v;} a[N];bool cmp(node a,node b) {return a.v*b.t<a.t*b.v;}int main() { // freopen("test.in","r",stdin);while(~scanf("%d%d",&n,&T)) {for(int i=0; i<n; i++)scanf("%d%d",&a[i].t,&a[i].v);sort(a,a+n,cmp);memset(dp,0,sizeof dp);for(int i=0; i<n; i++) {for(int j=T; j>=a[i].t; j–) {dp[j]=max(dp[j],dp[j-a[i].t]+a[i].v*j);}}printf("%lld\n",dp[T]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
才能做到人在旅途，感悟人生，享受人生。
