满大的窝,宋小姐,一不小心撞上坏首席
大佬每天给出的伤害是固有的，设dp[i,j]表述使得前i天结束时我的自信为j最少做水题的天数。d=max(i-dp[i,j])就是总共拿来给伤害的最大天数。打伤害一类是固定的伤害1，一类是积累伤害打出（最多用两次）。不妨暴力搜索积累伤害的情形c(d,f)，即我们用了d天积累了f的伤害。
若d>=hp每次伤害1就好了（直接判）；
若存在c使得f<=hp且f+d-d>=hp，这样累计一次大佬就好了（扫一遍）；
若存在c1c1使得f1+f2<=hp且d1+d2<=d且f1+f2+d-d1-d2>=hp，这样累计两次大佬就好了；先枚举c1(d1,f1)，则c2满足d2<=d-d1,f2<=hp-f1,同时也应最大化f2-d2以最大化总伤害。
噫要是没有d2<=d-d1的限制，我们可以把所有的c按照f排序，然后决策单调性.jpg（反过来的）就非常好做了。然后就可以发现若d1+d2>d，因为f1+f2<=hp，则f1+f2+d-d1-d2<hp不可能构成解。一语成谶
我要评论#include <bits/stdc++.h>
#define fr first
#define sc second
#define ll long long
using namespace std;
const int n=1e2+10;
const int m=3e6+10;
const int inf=0x3f3f3f3f;
int n,m,mc,tot,a[n],w[n];
int d,c[n],maxc,dp[n][n];
struct {
int cnt,head[m];
struct knode{int x,y,lst;} nd[m+1];
void insert(int x,int y) {
int t=(100ll*x+y)%m;
nd[++cnt]=(knode){x,y,head[t]},head[t]=cnt;
}
bool find(int x,int y) {
int t=(100ll*x+y)%m;
for(int i=head[t]; i; i=nd[i].lst)
if(x==nd[i].x&&y==nd[i].y) return 1;
return 0;
}
} vis;
struct snode{int f,d,l;};
queue<snode> q;
pair<int,int> v[m];
int main() {
scanf("%d%d%d",&n,&m,&mc);
for(int i=1; i<=n; ++i) scanf("%d",a+i);
for(int i=1; i<=n; ++i) scanf("%d",w+i);
memset(dp,inf,sizeof dp);
dp[0][mc]=0;
for(int i=1; i<=n; ++i) {
for(int j=a[i]; j<=mc; ++j) {
int x=j-a[i];
dp[i][x]=min(dp[i][x],dp[i-1][j]); x=min(mc,x+w[i]);
dp[i][x]=min(dp[i][x],dp[i-1][j]+1);
}
for(int j=0; j<=mc; ++j) d=max(d,i-dp[i][j]);
}
for(int i=1; i<=m; ++i) scanf("%d",c+i);
maxc=*max_element(c+1,c+m+1);
q.push((snode){1,1,0});
while(q.size()) {
snode x=q.front(); q.pop();
if(x.d==d||x.f>=maxc) continue;
q.push((snode){x.f,x.d+1,x.l+1});
if(x.l>1&&1ll*x.f*x.l<=maxc&&!vis.find(x.f*x.l,x.d+1)) {
v[++tot]=make_pair(x.f*x.l,x.d+1);
vis.insert(v[tot].fr,v[tot].sc);
q.push((snode){v[tot].fr,v[tot].sc,x.l});
}
}
sort(v+1,v+tot+1);
//printf("%d %d %d\n",d,maxc,tot);
for(int i=1; i<=m; ++i) {
if(c[i]<=d) {puts("1"); continue;}
int flag=0,mx=-inf;
for(int j=tot,k=1; j>=1; --j) {
while(k<tot&&v[k].fr+v[j].fr<=c[i]) mx=max(mx,v[k].fr-v[k].sc),++k;
if(v[j].fr-v[j].sc+mx+d>=c[i]) {flag=1; break;}
if(v[j].fr<=c[i]&&v[j].fr+d-v[j].sc>=c[i]) {flag=1; break;}
}
printf("%d\n",flag);
}
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论