題目鏈接：點擊查看

題目大意：給出 $n$ 次操作，初始時有一個 $k=0$，每次操作抽象為三個數 $txy$，其中 $x$ 可能為小數，可以選擇一個 $num\in [0,y]$，使得：

$t=1$：執行 $num$ 次 $k=?(k+x)?$

$t=2$：執行 $num$ 次 $k=?(k?x)?$

問對于 $[1,m]$ 的每個數，最少可以通過多少次操作獲得，如果無法獲得輸出 $?1$

題目分析：讀完題第一反應感覺是 $bfs$，但時間復雜度是 $O(n?m?m)$ 級別的，因為一共有 $n?m$ 個狀態，每個狀態又可以擴展出 $m$ 次，所以顯然是不可行的

看了題解后，發現這個模型也可以視為 $01$ 背包問題，其中，有 $n?m$ 個物品，背包容量是 $m$，如果直接暴力的話復雜度顯然也是 $O(n?m?m)$ 的

不過對于本題而言，有一個很重要的性質，也就是如果某個容量 $u$ 可以擴展到 $v$ ，且 $v$ 之前已經被更新過的話，那么就可以直接 $break$ 了，分兩種情況舉例一下就明白了：

假設 $u+t=v$，那么 $v+1$ 狀態，可以從 $u+t+1$ 更新，也可以從 $v+1$ 更新

假設 $u?t=v$，那么 $v?t$ 狀態，可以從 $u?t^2$ 更新，也可以從 $v?t$ 更新

所以綜上所述，每個狀態至多被更新一次，及時剪枝的話時間復雜度實際上是 $O(n?m)$ 的

代碼：

// Problem: D. Bananas in a Microwave // Contest: Codeforces - CodeCraft-21 and Codeforces Round #711 (Div. 2) // URL: https://codeforces.com/contest/1498/problem/D // Memory Limit: 256 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; const int base=1e5; bool dp[210][N]; LL t,x,y; int ans[N]; void update(LL &cur) {if(t==1) {cur=cur+(x+base-1)/base;} else {cur=(cur*x+base-1)/base;} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;memset(ans,-1,sizeof(ans));read(n),read(m);dp[0][0]=true;for(int i=1;i<=n;i++) {read(t),read(x),read(y);for(int j=0;j<=m;j++) {dp[i][j]=dp[i-1][j];}for(int j=0;j<=m;j++) {if(!dp[i-1][j]) {continue;}LL pos=j;for(int t=1;t<=y;t++) {update(pos);if(pos>m||dp[i-1][pos]) {break;}dp[i][pos]=true;ans[pos]=i;}}}for(int i=1;i<=m;i++) {printf("%d ",ans[i]);}return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1498D Bananas in a Microwave(思维+dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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