这个题目可以拆成两个部分:
首先你得苟得最久(第一部分),然后才是对别人对线(第二部分)。
第一个部分显然可以DP,设状态为$f_{i,j}$表示第$i$天,还有$j$点自信,有多少天不在苟(恢复自信)。
之后跟别人对线的话,可以利用最长不在苟的时间$Maxday$来判断。
由于有两次,设二元组$(f_1,d_1),(f_2,d_2)$,表示两次对线的伤害和攒伤害的天数。
大概有
$Maxday-d_1-d_2\ge 0\\f_1+f_2\le C\\f_1+f_2+(Maxday-d_1-d_2)\ge C$
用$bfs$求出所有合法二元组,用哈希表判重。
之后可以用双指针跑最优的$(f_i,d_i),(f_j,d_j)$
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int mod=514747,N=205;
const double pi=acos(-1);
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct Hashmap
{
struct edge{int f,d,next;}a[mod<<3];
int last[mod+5],len;
void ins(int f,int d)
{
int x=1ll*f*d%mod;
for(int k=last[x];k;k=a[k].next)
if(a[k].f==f&&a[k].d==d)return ;
a[++len]=(edge){f,d,last[x]};last[x]=len;
}
bool pd(int f,int d)
{
int x=1ll*f*d%mod;
if(!last[x])return 1;
for(int k=last[x];k;k=a[k].next)
if(a[k].f==f&&a[k].d==d)return 0;
return 1;
}
}H;
int dp[N][N],mc,w[N],a[N],Maxday,n;
inline int mn(int x,int y){return x<y?x:y;}
void prdp()
{
memset(dp,0xcf,sizeof(dp));dp[0][mc]=0;Maxday=0;
for(int i=1;i<=n;i++)
for(int j=a[i];j<=mc;j++)
if(dp[i-1][j]!=0xcfcfcfcf)
{
dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+1);
dp[i][mn(j+w[i]-a[i],mc)]=max(dp[i][mn(j+w[i]-a[i],mc)],dp[i-1][j]);
}
for(int i=1;i<=n;i++)
for(int j=0;j<=mc;j++)
Maxday=max(Maxday,dp[i][j]);
}
struct node
{
int d,l,f;
node(int d=0,int l=0,int f=0):d(d),l(l),f(f){}
}q[mod<<4];
struct Stack
{
int d,f;
Stack(int d=0,int f=0):d(d),f(f){}
bool operator <(const Stack a)const{return f==a.f?d<a.d:f<a.f;}
}sta[mod<<3];int cnt,Maxc;
void bfs()
{
int l=1,r=1;q[1]=node(1,0,1);
while(l<=r)
{
node x=q[l++];
if(x.d==Maxday)continue;
q[++r]=node(x.d+1,x.l+1,x.f);
if(x.l>1&&1ll*x.f*x.l<=Maxc&&H.pd(x.f*x.l,x.d+1))
{
q[++r]=node(x.d+1,x.l,x.f*x.l);
H.ins(x.f*x.l,x.d+1);sta[++cnt]=Stack(x.d+1,x.f*x.l);
}
}
sort(sta+1,sta+cnt+1);
}
int C[N],m;
void solve()
{
prdp();
bfs();
for(int t=1;t<=m;t++)
{
if(Maxday>=C[t]){puts("1");continue;}
int j=1,Max=0xcfcfcfcf,fl=0;
for(int i=cnt;j<i&&i>=1;i--)
{
while(j<i&&sta[i].f+sta[j].f<=C[t])Max=max(Max,sta[j].f-sta[j].d),++j;
if(sta[i].f<=C[t]&&sta[i].f-sta[i].d>=C[t]-Maxday){fl=1;break;}
if(j<i&&sta[i].f-sta[i].d+Max>=C[t]-Maxday){fl=1;break;}
}
qw(fl);puts("");
}
}
int main()
{
qr(n),qr(m),qr(mc);
for(int i=1;i<=n;i++)qr(a[i]);
for(int i=1;i<=n;i++)qr(w[i]);
for(int i=1;i<=m;i++)qr(C[i]),Maxc=max(Maxc,C[i]);
solve();
return 0;
}
最后一次更新于2020-03-22
0 条评论