博客

[SwordOJ Test Round #1]Solution of Happy Farming (#22)

2017-06-20 19:26:25 By ARZhu

Shocking! The Solutions of SwordOJ Test Round #1 in T3 is that...

It is obvious to realize that all the fields are equivalent. So we can just take one fields into consideration. And we can describe the states of the optimal solution as the number of time. Moreover, only $k$ online times should be considered. Thus, $f_i$, which i describes the ith time that Chroi can be online, for ith crop, deduces the state that is the moment when this crop is harvested which can be found by binary search. This way, we get a solution with a time complexity $O(mk\log k)$.

But, there is a better solution by Sennpai Shi! According to the analyze above, we can infer that we can deduce the state without binary search. Consider $f_i$ as the moment i, not the ith time that Chori can be online! Mark the harvesting time as $t_i$, the cost of the crop as $c_i$, the selling prize of the crop as $w_i$ and the set of online time as $S$. So the state transition equation is following: $$f_i=\left\{\begin{matrix} & f_{i-1},i \notin S\\ & f_{i-t_j}+w_j-c_j,i \in S \end{matrix}\right.$$

Notice that only when the pre-state is legal, which must be later than the first time when Chrio is online .And the time complexity is $O(mk)$ Here is the code:

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define d1(i,x) for(int i=x;i;--i)
#define f0(i,x) for(int i=0;i<=x;++i)
#define f1(i,x) for(int i=1;i<=x;++i)
#define f2(i,a,b) for(int i=a;i<=b;++i)
#define ll long long
using namespace std;
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N=3005;
int n,m,t,k,mx;
int f[N],pr[N],ti[N],va[N],fr[N];
bool isfr[N];
int main(){
f1(i,m){
}
f1(i,k){
isfr[fr[i]]=1;
mx=max(fr[i],mx);
}
sort( fr + 1, fr + 1 + k );
f0(i,mx){
if(i)f[i]=f[i-1];
if(isfr[i])f1(j,m)if(i-ti[j]>=fr[1]){
f[i]=max(f[i],f[i-ti[j]]+va[j]-pr[j]);
}
}
printf("%d\n",f[mx]*n);
}

LUCYOUNG

ARZhu
@LUCYOUNG
root
###非常好！
root

ARZhu
@root ### 吼啊！！
daxuezhastd
@mike
WD_louchenhao
@qaq
WD_louchenhao
@WD_louchenhao