2015
04-13

# Beat It!

There’s a monster-attacking game on the Renren’s open platform, and the game’s background are showing below.
Where lies a strange country, lices a strange monster. The strange people in that strange country are persecuted by the strange monster. So teh strange people make a strange cannon to defeat the strange monster.
As far as we know, the strange cannon is powerful, but once it works, it should not work in next T hours (Eg. If it fired at time 1, then time 2 to time T it cannot work). When the strange monster get hit during the daylight, it get PD point hurt; it will get PN point hurt when it happens during the night. As the country is strange, the time of the daylight and night changes eveyday. In the ith day, the daylight starts at time 1 and ends at time T1[i], then from time (T1[i]+1) to time (T1[i]+T2[i]) is night.
Here comes a question: what is the maximal hurt point would the strange monster got after N days?

First line contains an integer Q (1<=Q<=20), indicates the number of test cases.
For each case, first line contains 4 integers: N (1<=N<=1000), T (1<=T<=100), PD, PN.
Then followed N lines, the (i+1)th line contains 2 integer T1[i], T2[i].
(PD, PN, T1[i], T2[i] are all non-negative and fit the 32bit integer)

First line contains an integer Q (1<=Q<=20), indicates the number of test cases.
For each case, first line contains 4 integers: N (1<=N<=1000), T (1<=T<=100), PD, PN.
Then followed N lines, the (i+1)th line contains 2 integer T1[i], T2[i].
(PD, PN, T1[i], T2[i] are all non-negative and fit the 32bit integer)

1
2 5 20 5
6 10
2 1

Case 1: 65

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=500000+10;
typedef long long ll;
ll dp[maxn],num[maxn];
ll max(ll a,ll b)
{
return a>b?a:b;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int N,T,PD,PN,t,tcase=0;
scanf("%d",&t);
while(t--)
{
tcase++;
scanf("%d%d%d%d",&N,&T,&PD,&PN);
memset(dp,0,sizeof(dp));
int a,b,m=0,u=0;
ll ans=0;
for(int i=0;i<N;++i)
{
scanf("%d%d",&a,&b);
ll k;
if(a>2*T) k=(a-2*T)/T;
else k=0;
ans+=k*PD;
for(int j=0;j<a-k*T;++j)
num[++m]=PD;
if(b>2*T) k=(b-2*T)/T;
else k=0;
ans+=k*PN;
for(int j=0;j<b-k*T;++j)
num[++m]=PN;
}
// for(int i=1;i<=u;++i)
//{
for(int j=1;j<=m;++j)
{
if(j<=T)
{
dp[j]=max(num[j],dp[j-1]);
continue;
}
dp[j]=max(dp[j-1],dp[j-T]+num[j]);
}
//}
printf("Case %d: %I64d\n",tcase,ans+dp[m]);
}
return 0;
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.