烽火台网站,濮阳网站建设,wordpress另一更新,wordpress添加一级菜单D. Bananas in a Microwave
issue是fw题解 设计dp#xff1a; 状态表示#xff1a;fi,jf_{i,j}fi,j表示#xff1a;前iii个操作是否能够凑成jjj。
状态转移#xff1a;第iii次操作枚举操作次数考虑是否凑成val\text{val}val#xff0c;如果第i−1i-1i−1次操作也可以凑…D. Bananas in a Microwave
issue是fw题解 设计dp 状态表示fi,jf_{i,j}fi,j表示前iii个操作是否能够凑成jjj。
状态转移第iii次操作枚举操作次数考虑是否凑成val\text{val}val如果第i−1i-1i−1次操作也可以凑出val\text{val}val那么停止枚举次数立即break。
时间复杂度由于提前break能够控制在O(nm)O(nm)O(nm)
#includebits/stdc.husing namespace std;
using lllong long;const int N100010;
const ll INF0x3f3f3f3f3f3f3f3f;
int f[210][N];
int n,m,ans[N];
struct node
{int op;ll x;int y;
}q[N];
void update(ll u,int i)
{if(q[i].op1) uu(q[i].x99999)/100000;elseu(u*q[i].x99999)/100000;
}
int main()
{cinnm;for(int i1;in;i) cinq[i].opq[i].xq[i].y;memset(ans,-1,sizeof ans);f[0][0]1;for(int i1;in;i)for(int j0;jm;j){f[i][j]|f[i-1][j];if(!f[i-1][j]) continue;ll curj;for(int k1;kq[i].y;k){update(cur,i);if(curm||f[i-1][cur]) break;ans[cur]i;f[i][cur]1;}}for(int i1;im;i) coutans[i] ;cout\n;
}
