Time-6 - Make you Stronger

2 secs 1024 MB

matcharate12

問題

提出

テストケース

解説

この問題は個数制限なしナップザック問題を問います。

$T=0$ のとき...

一旦簡単のため $T=0$ のことについて考えてみましょう。そうすると次の問題と同値であることが言えます。

子スライムを何匹か繰り返し選び、それらのぷるぷる度の合計値が $K$ 以下となるように親スライムに合成した後、考えられる価値の最大値はいくつか？

これは、単なる個数制限なしナップザック問題であることがわかります。例えば

$\text{dp}[i][j]:=$ $i$ 個目の子スライムを選んでぷるぷる度の合計を $j$ にしたときの価値の最大値

といったDP(動的計画法)テーブルを定義しましょう。最初 $i=1,2,...,N,\ j=0,1,2,...,K$ に対して $\text{dp}[i][j]=0$ と初期化します。
その後、次のように遷移式を立てます。

$\text{dp}[i+1][j]=\text{dp}[i][j]$ (子スライム $i$ を $1$ 匹も選ばないとき)
$\text{dp}[i+1][j]=\max(\text{dp}[i+1][j],\text{dp}[i+1][j-A_i]+B_i)$ (子スライム $i$ を $1$ 匹以上選ぶ場合)

最終的に答えるべき値は $\max(\text{dp}[N][j])$ です。
※この漸化式の説明はここでは省略します。Webでは分かりやすい記事も転がってるはずなので、そちらを参考にしてください。

$T\ge 1$ のとき...

$T=0$ を考えた上で、元の問題を考えてみます。
実は、 $t=0,1,2,...,T$ におけるそれぞれの子スライムのステータスを保管しながら、同じように動的計画法を用いることで解くことが可能です。

入力では $t=0$ の場合のみですが、それに $t=1,2,...,T$ を同じように入力している、と考えると分かりやすいと思われます。

以上から全体で $O(NTK)$ で実装することができます。以下が解答例(C++,Python)となります。

追記(14:42更新)

実はこの問題、答えが -1 になることはありません。 $K=0$ だとしてもスライムを一匹も選ばないことが最適であるためです。

(下のコードは追記前のコードにしてあります)

C++

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(A)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge {
    int to;
    ll cost;
    //int from;
};
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<int>>;
using EGraph = vector<Edge>;
using SGraph = vector<set<ll>>;
template <typename T>
int siz(T& a){ return (int)a.size(); }
ll squa(ll x){ return x*x; }
using namespace std;
​
ll dp[10101][1010];
int main(){
    int n,k,t; cin >> n >> k >> t;
    vector<P> state;
    rep(_,n){
        int a,b; cin >> a >> b;
        rep(i,t+1){
            state.push_back({a,b});
            a++; b++;
        }
    }
​
    n = siz(state);
    rep(i,n){
        rep(j,k+1){
            int pr = state[i].first,val = state[i].second;
​
            dp[i+1][j] = dp[i][j];
            if(j-pr >= 0) dp[i+1][j] = max(dp[i+1][j],dp[i+1][j-pr]+val);
        }
    }
​
    ll ans = 0;
    rep(i,k+1) ans = max(ans,dp[n][i]);
    cout << (ans == 0 ? -1 : ans);
}
​

Python

xxxxxxxxxx
 
n,k,t = list(map(int,input().split()))
state = []
for i in range(n):
    a,b = list(map(int,input().split()))
    for _ in range(t+1):
        state.append([a,b])
        a += 1
        b += 1
​
dp = [[0 for i in range(k+1)] for j in range(len(state)+1)]
for i in range(len(state)):
    for j in range(k+1):
        dp[i+1][j] = dp[i][j]
        if j-state[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i+1][j-state[i][0]]+state[i][1])
​
ans = 0
for i in range(k+1): ans = max(ans,dp[len(state)][i])
print(-1 if ans == 0 else ans)

Time-6 - Make you Stronger

T=0T=0T=0 のとき...

T≥1T\ge 1T≥1 のとき...

追記(14:42更新)

$T=0$ のとき...

$T\ge 1$ のとき...