D. Bananas in a Microwave

題意：

u1s1，題意真難懂
有n個時間，每個時間給你兩個操作，第一個是k=k+x，第二個是k=k?x，且可以執(zhí)行[0,y]次，（在第i個時間點(diǎn)，必須應(yīng)用第i個操作）
k 初始狀態(tài)為0，
現(xiàn)在讓你依次輸出從1到m，到達(dá)每個數(shù)最少的操作次數(shù)

題解：

滿腦子都是暴力。。但是暴力肯定不行
有點(diǎn)背包問題的感覺？但是第二種操作怎么都不能有效實(shí)現(xiàn)
看來終究還是暴力
根據(jù)題意可以知道最后的步數(shù)范圍也就是[1,n]
最直接暴力是O(n*m^2),遍歷[1,n]，嘗試[0,y]次相應(yīng)操作，y的范圍是[0,m]
比如原本能到的數(shù)是[3,11]，現(xiàn)在x =4，y = 4，對于每個數(shù)更新的時候遍歷到的集合就是[3,7,11,15,19]和[11,15,19,23,27]，11的位置重復(fù)出現(xiàn)，所以當(dāng)我們加數(shù)的時候，如果當(dāng)前數(shù)已經(jīng)存在，就直接break

總結(jié)：
先將所有位置初始化為inf，第0位是0
每次從m到0循環(huán)，看哪個數(shù)已經(jīng)被確定了（第一次因為只有位置0還未確定，所以會從0開始），然后就在那個數(shù)的基礎(chǔ)上繼續(xù)擴(kuò)展，出現(xiàn)已經(jīng)確定的就break
復(fù)雜度是（n * m * 2）

代碼：

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define forn(i,x,n) for(int i = x;i <= n;++i) #define forr(i,x,n) for(int i = n;i >= x;--i)const int N = 1e6+7,INF = 1e9; int ans[N];int main() {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) ans[i] = INF;for(int cur=1;cur<=n;cur++){ll t,x,y;scanf("%lld%lld%lld",&t,&x,&y);for(int i=m;i>=0;i--){if(ans[i] == INF) continue;ll z = i;for(int j=1;j<=y;j++){if(t == 1) z = z + (x + 100000 - 1) / 100000;else z = (z * x + 100000 - 1) / 100000;if(z > m) break;if(ans[z] < INF) break;ans[z] = cur;}}}forn(i,1,m) printf("%d ",ans[i] == INF ? -1 : ans[i]);puts("");return 0; }

總結(jié)

以上是生活随笔為你收集整理的D. Bananas in a Microwave的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。