題目描述

人們總是難免會碰到大佬。他們趾高氣昂地談論凡人不能理解的算法和數據結構，走到任何一個地方，大佬的氣場就能讓周圍的人嚇得瑟瑟發抖，不敢言語。 你作為一個 OIER，面對這樣的事情非常不開心，于是發表了對大佬不敬的言論。 大佬便對你開始了報復，你也不示弱，揚言要打倒大佬。

現在給你講解一下什么是大佬，大佬除了是神犇以外，還有著強大的自信心，自信程度可以被量化為一個正整數 C（ 1<=C<=10^8）， 想要打倒一個大佬的唯一方法是摧毀 Ta 的自信心，也就是讓大佬的自信值等于 0（恰好等于 0，不能小于 0）。 由于你被大佬盯上了，所以你需要準備好 n(1<=n<=100)天來和大佬較量，因為這 n 天大佬只會嘲諷你動搖你的自信，到了第n+1 天，如果大佬發現你還不服，就會直接虐到你服，這樣你就喪失斗爭的能力了。

你的自信程度同樣也可以被量化，我們用 mc (1 <= mc <= 100)來表示你的自信值上限。

在第 i 天（ i>=1），大佬會對你發動一次嘲諷，使你的自信值減小 a[i]，如果這個時刻你的自信值小于 0 了，那么你就喪失斗爭能力，也就失敗了（特別注意你的自信值為 0 的時候還可以繼續和大佬斗爭）。 在這一天， 大佬對你發動嘲諷之后，如果你的自信值仍大于等于 0，你能且僅能選擇如下的行為之一：

還一句嘴，大佬會有點驚訝，導致大佬的自信值 C 減小 1。

做一天的水題，使得自己的當前自信值增加 w[i], 并將新自信值和自信值上限 mc 比較，若新自信值大于 mc，則新自信值更新為 mc。例如， mc=50， 當前自信值為 40， 若w[i]=5，則新自信值為 45，若 w[i]=11，則新自信值為 50。

讓自己的等級值 L 加 1。

讓自己的諷刺能力 F 乘以自己當前等級 L，使諷刺能力 F 更新為 F*L。

懟大佬，讓大佬的自信值 C 減小 F。并在懟完大佬之后，你自己的等級 L 自動降為 0，諷刺能力 F 降為 1。由于懟大佬比較掉人品，所以這個操作只能做不超過 2 次。

特別注意的是，在任何時候，你不能讓大佬的自信值為負，因為自信值為負，對大佬來說意味著屈辱，而大佬但凡遇到屈辱就會進化為更厲害的大佬直接虐飛你。在第 1 天，在你被攻擊之前，你的自信是滿的（初始自信值等于自信值上限 mc）， 你的諷刺能力 F 是 1， 等級是 0。

現在由于你得罪了大佬，你需要準備和大佬正面杠，你知道世界上一共有 m（ 1<=m<= 20）個大佬，他們的嘲諷時間都是 n 天，而且第 i 天的嘲諷值都是 a[i]。不管和哪個大佬較量，你在第 i 天做水題的自信回漲都是 w[i]。 這 m 個大佬中只會有一個來和你較量（ n 天里都是這個大佬和你較量），但是作為你，你需要知道對于任意一個大佬，你是否能摧毀他的自信，也就是讓他的自信值恰好等于 0。和某一個大佬較量時，其他大佬不會插手。

輸入輸出格式

輸入格式：

?

第一行三個正整數 n,m,mc。分別表示有 n 天和 m 個大佬, 你的自信上限為 mc。

接下來一行是用空格隔開的 n 個數，其中第 i(1<=i<=n)個表示 a[i]。

接下來一行是用空格隔開的 n 個數，其中第 i(1<=i<=n)個表示 w[i]。

接下來 m 行，每行一個正整數，其中第 k(1<=k<=m)行的正整數 C[k]表示第 k 個大佬的初始自信值。

?

輸出格式：

?

共 m 行，如果能戰勝第 k 個大佬（讓他的自信值恰好等于 0），那么第 k 行輸出 1，否則輸出 0。

?

輸入輸出樣例

輸入樣例#1：
30 20 30 15 5 24 14 13 4 14 21 3 16 7 4 7 8 13 19 16 5 6 13 21 12 7 9 4 15 20 4 13 12 22 21 15 16 17 1 21 19 11 8 3 28 7 10 19 3 27 17 28 3 26 4 22 28 15 5 26 9 5 26 30 10 18 29 18 29 3 12 28 11 28 6 1 6 27 27 18 11 26 1 輸出樣例#1：
0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1 0 0 1

說明

20%數據保證: 1≤n≤10。

另有 20%數據保證:1 ≤ C[i],n,mc ≤ 30。

100%數據保證: 1 ≤ n,mc ≤ 100; 1≤m≤20; 1≤a[i],w[i]≤mc; 1≤C[i] ≤10^8

題解：

dp+搜索+單調棧

首先設f[i][j]為前i天，自信值為j時不刷題能活多少天

f[i][j-a[i]]=f[i-1][j]+1,f[i][min(mc,j-a[i]+w[i])]=f[i-1][j]

計算出自由的最大時間day

接下來要算出d[f][l]，為嘲諷能力f，等級l的最小天數

因為f，l值太大，這里用map，也可以用數組分別f，l記錄下標

這個過程用bfs就行了，有個剪支就是當天數大于day時則舍去，可以減少map的大小

用一個數組記錄下所有二元組{f,d[f][l]}由于數組只與f有關，所以對于相同的f，只要d最小

由于可以不懟，加入{0,0}

兩次懟滿足條件day-d1-d2>=c-f1-f2,f1+f2<=c

即day-c>=d1-f1+d2-f2

按f排序后，用單調棧

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<map> 6 using namespace std; 7 struct data 8 { 9 int f,d; 10 }s[5000001]; 11 int qf[5000001],ql[5000001],maxc,f[110][110],day,cnt,n,m,mc,a[110],w[110],c[111]; 12 int vis[10000001]; 13 map<int,map<int,int> > d; 14 bool cmp(data a,data b) 15 { 16 return a.f<b.f; 17 } 18 void bfs() 19 {int head,tail,i; 20 qf[1]=1;ql[1]=0; 21 d[1][0]=1; 22 head=0;tail=1; 23 while (head<tail) 24 { 25 head++; 26 int nowf=qf[head],nowl=ql[head]; 27 if (d[nowf][nowl]==day) continue; 28 if (!d[nowf][nowl+1]) 29 { 30 tail++; 31 qf[tail]=nowf,ql[tail]=nowl+1; 32 d[nowf][nowl+1]=d[nowf][nowl]+1; 33 } 34 if ((long long)nowf*nowl<=maxc&&!d[nowf*nowl][nowl]) 35 { 36 tail++; 37 qf[tail]=nowf*nowl; 38 ql[tail]=nowl; 39 d[nowf*nowl][nowl]=d[nowf][nowl]+1; 40 } 41 } 42 s[++cnt]=(data){0,0}; 43 vis[0]=1; 44 for (i=1;i<=tail;i++) 45 if (vis[qf[i]]==0) 46 { 47 s[++cnt]=(data){qf[i],d[qf[i]][ql[i]]}; 48 vis[qf[i]]=cnt; 49 } 50 else 51 { 52 s[vis[qf[i]]].d=min(s[vis[qf[i]]].d,d[qf[i]][ql[i]]); 53 } 54 } 55 int main() 56 {int i,j,k; 57 bool flag; 58 cin>>n>>m>>mc; 59 for (i=1;i<=n;i++) 60 scanf("%d",&a[i]); 61 for (i=1;i<=n;i++) 62 scanf("%d",&w[i]); 63 for (i=1;i<=m;i++) 64 scanf("%d",&c[i]),maxc=max(maxc,c[i]); 65 for (int i=0;i<=n;++i) 66 for (int j=0;j<=101;++j) f[i][j]=-n; 67 f[0][mc]=0; 68 for (i=1;i<=n;i++) 69 { 70 for (j=a[i];j<=mc;j++) 71 { 72 f[i][j-a[i]]=max(f[i][j-a[i]],f[i-1][j]+1); 73 int p=min(j-a[i]+w[i],mc); 74 f[i][p]=max(f[i][p],f[i-1][j]); 75 } 76 } 77 for (i=0;i<=n;i++) 78 { 79 for (j=0;j<=mc;j++) 80 day=max(day,f[i][j]); 81 } 82 //cout<<day<<endl; 83 bfs(); 84 //cout<<cnt<<endl; 85 sort(s+1,s+cnt+1,cmp); 86 //for (i=1;i<=cnt;i++) 87 //cout<<s[i].f<<' '<<s[i].d<<endl; 88 for (i=1;i<=m;i++) 89 {flag=0;k=1;int v=2e9; 90 for (j=cnt;j;j--) 91 {//cout<<j<<' '<<k<<endl; 92 while (s[j].f+s[k].f<=c[i]&&k<j) 93 v=min(v,s[k].d-s[k].f),k++; 94 if (day-c[i]>=v+s[j].d-s[j].f) flag=1; 95 if (flag) break; 96 } 97 printf("%d\n",flag); 98 } 99 }

?

轉載于:https://www.cnblogs.com/Y-E-T-I/p/7288935.html

總結

以上是生活随笔為你收集整理的[AH/HNOI2017]大佬的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。