2015
09-17

# Harvest Moon

Harvest Moon (牧�鑫镎Z Bokujō Monogatari) is a virtual role playing game for the Super Nintendo Entertainment System developed and published by Pack-In-Video (now Marvelous AQL), first released in Japan in 1996, and 1997 in North America. This is the first game in the long-running Harvest Moon titles. A PAL version was released by Nintendo in early 1998 for Western Europe and Oceania, with language localizations for Germany and France.
– wikipedia

Hard though, it’s still an incorrigibly temptation for Moor. In the game, Moor’s favorite is to cultivate in his own pasture. His pasture is large – we may consider it as a w×h lattice.
The shop sells A kinds of seeds. The price of the ith seed is Q_i dollars, and it can be sowed to cover a 3×3 lattice. Note that the cover area may contain the grids outside his pasture, but only the grids inside belong to him. Further more, although a grid may be sowed multiple times, the later sowing on this grid exert nothing if the corns are still growing in it.
After ploughing and weeding, the corns get ripe right after N_i days and Moor will go harvest. For instance, if Moor sows the seeds at the beginning of day x, they will get ripe at the beginning of the (x+N_i)th day(or you may consider it as the right end of the (x+N_i-1)th day). After harvest, some of the corns will disappear and the grids they belong to would become empty, while the others may stays and get ripe again and again, in a period of M_i days. For convenience, Moor always leaves the second kind of corns staying, but he will try to keep sowing in those new empty grids. Moor only sows seeds and harvest at the beginning or ending of some day, and you may assume it wastes no time for Moor to make operations.
Initially, Moor’s got Y dollars. When selling a 1×1 grid of corns, he will obtain P_i dollars back. Moor wonders the maximum dollars he will get at the end of the Dth day, if he buys only one kind of seeds? Certainly, he may do nothing and keep all dollars in his pocket.

The input contains several test cases.
An integer T(T≤110) will exist in the first line of input, indicating the number of test cases.
Each test case begins with 5 integers w,h,A,D,Y(3≤w,h≤100,0<A,D≤1000,0<Y≤100000).
The following A lines, each with 4 integers Q_i,P_i,N_i,M_i (0<Q_i,P_i≤1000;N_i,M_i≤10000), describe the property of the ith seed. M_i=0 denotes that the seed will not get ripe again after harvest.

The input contains several test cases.
An integer T(T≤110) will exist in the first line of input, indicating the number of test cases.
Each test case begins with 5 integers w,h,A,D,Y(3≤w,h≤100,0<A,D≤1000,0<Y≤100000).
The following A lines, each with 4 integers Q_i,P_i,N_i,M_i (0<Q_i,P_i≤1000;N_i,M_i≤10000), describe the property of the ith seed. M_i=0 denotes that the seed will not get ripe again after harvest.

1
3 3 2 3 100
100 90 3 0
100 90 2 0

810

< Q_i, P_i ≤ 1000; N_i, M_i ≤ 10000
)。

——>>传参时类型声明为了int，一直WA无数。。。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 1000 + 10;
const int maxm = 9 + 5;

int w, h, A, D;
long long Y;
int Q[maxn], P[maxn], N[maxn], M[maxn];
int num[maxm];      //num[i]表示9个格子中占了i个有效格子的种子数
int remain[maxm];       //remain[i]表示在种植了其中的一些种子后，剩余空地中9个格子中占了i个有效格子的种子数
int harvestGrid[maxn];      //harvestGrid[i]表示i天后有收获的土地格子数
int blank[maxn];        //blank[i]表示第i天有多少空地可以种植
int p;      //一个种子，尽量种在占格子尽量多的地方
int now;        //现在是第几天

scanf("%d%d%d%d%I64d", &w, &h, &A, &D, &Y);
for(int i = 1; i <= A; i++) scanf("%d%d%d%d", &Q[i], &P[i], &N[i], &M[i]);
}

void init(){
memset(num, 0, sizeof(num));
num[9] = (w/3) * (h/3);     //左上方
int ww = w % 3, hh = h % 3;
num[9-(3-ww)*(3-hh)]++;     //右下角
num[3*hh] += w/3 - 1;       //左下方
num[3*ww] += h/3 - 1;       //右上角
num[ww*hh] += 2;        //左下方与右下角中间的部分和右上角与右下角之间的部分
}

bool isok(int x){       //判断这种种子是否值得购买
if(!M[x]) return (long long)P[x] * p > Q[x] ? 1 : 0;      //时间要够，要能赚钱
else return (long long)(1 + (D - now - N[x]) / M[x]) * p * P[x] > Q[x] ? 1 : 0;        //时间不够的话求出的是非正数，一样可以判
}

long long work(int x, long long money){
if(D - now < N[x]) return money;        //时间不够，直接返回
while(p >= 1){
if(!isok(x)){       //看看是否应该买种子
p = 0;      //没有收获的话，不用再往下扫描，因为格子越少，赚得越少，下面的一定赚不了
break;
}
//最终有收获，该买
int numOfBuy = (remain[p] < money / Q[x]) ? remain[p] : money / Q[x];        //能买到的种子的个数
money -= Q[x] * numOfBuy;       //用去了一部分钱
harvestGrid[now+N[x]] += numOfBuy * p;      //更新那些可以收获的日子
if(!remain[p]) p--;
else break;     //没钱了
}
return money;
}

long long cal(int x){
memset(harvestGrid, 0, sizeof(harvestGrid));        //初始时没种种子，哪一天都没有收获
memcpy(remain, num, sizeof(num));       //初始时所有空地都没种种了，故remain == num
memset(blank, 0, sizeof(blank));        //初始化
p = 9;
now = 0;
long long money = work(x, Y);        //第一次购买完种子后剩下的钱
for(now = 1; now <= D; now++){      //模拟D天的收获
if(!harvestGrid[now]) continue;
money += harvestGrid[now] * P[x];      //可以收获的话
if(!M[x] && D - now >= N[x]){       //在时间足够的前提下，将刚刚收获的土地继续种植
money -= Q[x] * blank[now];       //用去了一部分钱
harvestGrid[now+N[x]] += harvestGrid[now];      //更新那些可以收获的日子
blank[now+N[x]] += blank[now];        //那天会新空出的空地，是值得种植并且能够种植的（赚的钱比原来的成本更多了）（在时间允许下）
}
else if(M[x] && D - now >= M[x]){        //在时间足够的前提下，将刚刚收获的土地继续收获
harvestGrid[now+M[x]] += harvestGrid[now];      //更新那些可以收获的日子
}
money = work(x, money);
}
return money;
}

void solve(){
long long Max = -1;
for(int i = 1; i <= A; i++) Max = max(Max, cal(i));
printf("%I64d\n", Max);
}

int main()
{
int T;
scanf("%d", &T);
while(T--){
init();
solve();
}
return 0;
}