相关链接
题目传送门: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; }