相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4828
解题报告
先$DP$出最多可以有多少天不做题
然后我们发现两次$D$人其实是独立的
于是我们再$DP$出攻击达到$x$的最小天数
最后回答每个询问的时候
用个双指针扫一扫
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 109;
const int M = 930000;
int n,m,mc,tot,MX,ispri[N],w[N],a[N],f[N][N];
pair<int,int> itm[M];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
void DFS(int t, LL sum) {
if (t > MX) return;
else {
DFS(t + 1, sum);
if (ispri[t]) {
for (;sum*=t,sum<=1e8;) {
itm[++tot].first = sum;
DFS(t + 1, sum);
}
}
}
}
inline int cal(int x) {
int ret = x + 1;
for (int i=min(MX,x-1),cnt,tmp;i;i--) {
if (x % i) continue;
cnt = i + 1; tmp = x;
for (int j=i;j>1&&tmp>1;j--) {
while (tmp % j == 0) {
tmp /= j;
++cnt;
}
}
if (tmp == 1) {
ret = min(ret, cnt);
} else {
break;
}
}
return ret;
}
int main() {
n = read(); m = read(); mc = read();
for (int i=1;i<=n;i++) {
a[i] = read();
}
for (int j=1;j<=n;j++) {
w[j] = read();
}
//DP最多空出来的天数
memset(f, -1, sizeof(f));
f[1][mc] = 0;
for (int i=1;i<=n;i++) {
for (int j=a[i];j<=mc;j++) {
if (f[i][j] == -1) continue;
int t1 = min(j - a[i] + w[i], mc), t2 = j - a[i];
if (t1 >= 0) {
f[i + 1][t1] = max(f[i + 1][t1], f[i][j]);
}
if (t2 >= 0) {
f[i + 1][t2] = max(f[i + 1][t2], f[i][j] + 1);
}
}
}
MX = -1;
for (int j=2;j<=n+1;j++) {
for (int i=0;i<=mc;i++) {
MX = max(MX, f[j][i]);
}
}
//搞出每一个物品的最小花费
for (int j=2;j<=100;j++) {
ispri[j] = 1;
for (int i=2;i*i<=j;i++) {
if (j % i == 0) {
ispri[j] = 0;
}
}
}
DFS(1, 1);
for (int i=1;i<=tot;i++) {
itm[i].second = cal(itm[i].first);
}
itm[++tot] = make_pair(0, 0);
sort(itm+1, itm+1+tot);
//对于每个询问用一个双端队列
for (int tt=1;tt<=m;tt++) {
int C = read(), ans = 0;
for (int i=tot,pfx=1,cur=-1e9;i;i--) {
while (pfx <= tot && itm[pfx].first <= C - itm[i].first) {
cur = max(cur, itm[pfx].first - itm[pfx].second);
pfx++;
}
if (cur + itm[i].first - itm[i].second >= C - MX) {
ans = 1;
break;
}
}
printf("%d\n",ans);
}
return 0;
}