前言

你所能够依靠的，只有你自己。

题目

CF

洛谷

题目大意：

输入两个整数 \(n,m\) 表示操作数与目标香蕉数量。

接下来输入 \(n\) 个操作，每个操作有三个整数 \(t_i,x_i,y_i\)。令你当前的香蕉数量为 \(k\)。

• 如果 \(t_i=1\)，你可以从 \([0,y_i]\) 中选择一个数 \(a_i\) ，将 \(\lceil k+x_i\rceil\) 赋值给 \(k\)，此步骤执行 \(a_i\) 次。
• 如果 \(t_i=2\)，你可以从 \([0,y_i]\) 中选择一个数 \(a_i\) ，将 \(\lceil k\cdot x_i\rceil\) 赋值给 \(k\)，此步骤执行 \(a_i\) 次。

对于每一个 \(i\in[1,m]\) 输出最少操作次数使得你的香蕉数量变为 \(i\)。如果不能做到，输出 \(-1\)。

注意： \(x_i\) 可以是一个小数。

特别地，题目中的 \(x_i\) 以 \(x_i'\) 的形式输入，\(x_i'=x_i*10^5\)。

\(1\le n\le 200;2\le m\le 10^5;1\le t_i\le 2;1\le y_i \le m.\)

对于第一种操作：\(1\le x_i'\le 10^5\cdot m.\)

对于第二种操作：\(10^5< x_i'\le 10^5\cdot m.\)

讲解

看似是个 \(O(nm^2)\) 的多重背包，但实际上可以用完全背包的思路做。

思路一

假设我们什么结论都没有得出来，考虑直接 \(\tt DP\)。

我们令 \(dp_i\) 表示得到 \(i\) 根香蕉的最小操作数，\(cnt_i\) 表示当前操作下得到 \(i\) 根香蕉的最小步骤数。

直接类完全背包即可。

时间复杂度 \(O(nm).\)

思路二

依然是背包，但我们先考虑证明一个结论：

如果操作相同，那么如果要得到的香蕉数量为 \(i\)，最多存在一个 \(j\) 使得 \(j\) 经过一次步骤的变换后变成 \(i\)。

操作一：显然。

操作二：考虑反证。

假设存在两个数 \(j_1,j_2,j_1<j_2<i\) 使得这两个数经过一次变换后可以变成 \(i\)。令 \(x_i\) 的整数部分为 \(A_i(A_i\ge1,A_i\in N^+)\)，小数部分为 \(B_i(0\le B_i<1)\)。

那么经过变换后两个数就是 \(i_1=j_1*A_i+\lceil j_1*B_i\rceil,i_2=j_2*A_i+\lceil j_2*B_i\rceil\)。

显然有 \(j_1*A_i<j_2*B_i,\lceil j_1*B_i\rceil\le\lceil j_2*B_i\rceil\)。

那么 \(i_1<i_2\)，原命题不成立。

所以我们就可以直接暴力做，对于每一个之前可以得到的香蕉数，暴力更新其可以得到的香蕉数，如果更新到的香蕉数之前可以得到，那么就可以退出循环。

时间复杂度依然是 \(O(nm)\)。详见std。

坑点

• 上取整的时候先乘再除，或者手写上取整函数，不要相信 \(\tt double\) 的精度。

• \(\tt int\) 会爆。

代码

思路一：

LL dp[MAXM],cnt[MAXM];
 
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%lld %lld",&n,&m);
	for(int i = 1;i <= m;++ i) dp[i] = INF;
	for(int i = 1;i <= n;++ i)
	{
		double opt,x1,y;
		scanf("%lf %lf %lf",&opt,&x1,&y);
		double x = x1 / 100000.0;
		for(int j = 0;j <= m;++ j)
			if(dp[j] == INF) cnt[j] = INF;
			else cnt[j] = 0;
		for(int j = 0;j <= m;++ j)
		{
			if(dp[j] == INF) continue;
			LL W;
			if(opt == 1) W = (LL)ceil(j+x);
			else W = (LL)ceil(j*x1/100000);
			if(W <= m)
				if(cnt[j]+1 < cnt[W] && cnt[j] < y) dp[W] = i,cnt[W] = cnt[j]+1;
		}
	}
	for(int i = 1;i <= m;++ i)
		if(dp[i] == INF) printf("-1 ");
		else printf("%lld ",dp[i]);
	return 0;
}

思路二：(std)

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

const int DIV = 1e5;
inline LL ceil(LL x, LL y) {
    return (x + y - 1) / y;
}

int main() {
    int T, M; cin >> T >> M;

    vector<bool> is_seen(M + 1, false);
    is_seen[0] = true;
    vector<int> answer(M + 1, -1);
    answer[0] = 0;

    for (int timestep = 1; timestep <= T; timestep++) {
        auto new_is_seen = is_seen;

        int t, y; LL x;
        cin >> t >> x >> y;

        auto operation = [&] (long long &curr) {
            if (t == 1) {
                curr = curr + ceil(x, DIV);
            } else {
                curr = ceil(curr * x, DIV);
            }
        };

        for (int k = 0; k <= M; k++) {
            if (is_seen[k]) {
                long long curr = k;
                operation(curr);

                for (int a = 1; a <= y;) {//直接暴力更新
                    if (curr > M) break;
                    if (is_seen[curr]) break;
                    
                    new_is_seen[curr] = true;
                    answer[curr] = timestep;

                    a++;
                    operation(curr);
                }
            }
        }

        is_seen = new_is_seen;
    }

    for (int i = 1; i <= M; i++)
        cout << answer[i] << " ";

    cout << endl;
}