UOJ Logo ARZhu的博客

博客

[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;
inline int read(){
    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(){
    n=read();m=read();
    t=read();k=read();
    f1(i,m){
        pr[i]=read();
        ti[i]=read();
        va[i]=read();
    }
    f1(i,k){
        fr[i]=read();
        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
这里居然不支持markdown。
ARZhu
@root ### 吼啊!!
daxuezhastd
@mike
WD_louchenhao
@qaq
WD_louchenhao
@WD_louchenhao

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。