正題

題目鏈接:https://ac.nowcoder.com/acm/contest/11254/A

---

題目大意

現在有一個$y\in [1,n]$，$Bob$每次可以選擇問$Alice$是否$y\ge x$，$Alice$可以說一次謊。$Bob$要在最少次數內確定$y$的值，而$Alice$盡量使得次數最多。

現在已知第一次$Bob$詢問的是$k$且$Alice$回答了是，對于$k\in [1,n]$求每個$k$ $Bob$需要的最少詢問次數。

$1\le n\le 2000$

---

解題思路

$dls$ 在 WC 講的神仙題目。

對于一種情況，假設$y=i$時，$Alice$說謊的次數是固定的，記這個次數為$a_i$，所以如果當$1～n$中只有一個數字滿足$a_i\le 1$時那么答案就是這個數字了。

然后看$Bob$的操作，它每次可以選擇一個$x$，$Alice$可以選擇讓$\ge x$的數字或者讓$<x$的數字的位置$a_i=a_i+1$，$Bob$需要用最少的次數使得只有一個位置$a_i\le 1$。

發現因為每次都是覆蓋一個前綴或者一個后綴，所以如果只保留$a_i=0/1$的話那么所有的狀態肯定是若干個$1$+若干個$0$+若干個$1$，分別記為$a/b/c$個，我們就可以設狀態為$f_{a,b,c}$進行轉移。

考慮到隨著$c$的增大我們肯定會盡量選擇中間的位置，也就是決策位置是單調遞增的，所以我們可以做到$O(n^3)$的轉移。

然后注意到這個和猜數字的規則很像，詢問次數級別不會超過$\log n$，所以我們可以考慮交換次數和一個值域，記$f_{w,a,b}$表示猜測了$w$次能夠猜出來的$a$個$0$+$b$個$1$+$c$個$0$中最大的$c$，然后用決策單調性轉移。

時間復雜度：$O(n^2\log n)$

---

code

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=2100;int n,inf,f[20][N][N];int calc(int u,int v){int ans=19;while(ans&&f[ans-1][u][v]>=0)ans--;return ans;}int main(){scanf("%d",&n);memset(f,0xcf,sizeof(f));inf=f[0][0][0];for(int i=0;i<=1;i++)for(int j=0;j<=1-i;j++)f[0][i][j]=1-i-j;for(int i=1;i<=19;i++){for(int j=0;j<=n;j++)for(int k=0;k<=j;k++){int u=f[i-1][j-k][k];int v=f[i-1][k][j-k];if(u!=inf&&v!=inf){u=min(u,n-j);f[i][u][j]=max(f[i][u][j],v);}}for(int j=0;j<=n;j++){int v=f[i-1][j][0];if(v!=inf){for(int k=0;k<=n-j;k++){int u=f[i-1][k][j];if(u==inf)break;f[i][min(u,n-j)][j]=max(f[i][min(u,n-j)][j],v+k);f[i][min(v+k,n-j)][j]=max(f[i][min(v+k,n-j)][j],u);}}}for(int j=0;j<=n;j++)for(int k=n-j-1;k>=0;k--)f[i][k][j]=max(f[i][k][j],f[i][k+1][j]);}for(int i=0;i<n;i++)printf("%d ",calc(i,n-i));return 0;}

總結

以上是生活随笔為你收集整理的2021牛客暑期多校训练营3A-Guess and lies【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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