予鈴

競プロとか備忘録とか…

典型ナップサックを1次元配列で解く。

B - 書き換え(Rewrite) の問題を解く。

二次元DPで解くと、

 dp[j][i] := 時間jの時にi個書類を選んだ(or使わなかった)ときの最大値で

dp[j+t[i+1][i+1]=max (dp[j+t[i]][i+1],dp[j][i]+v[i+1]) という漸化式になる。

dp[i] :=時間iのときの最大の価値 
となるdp配列を考えます。

①dp配列を逆順(mから0)に更新していくと、重複して更新することが無い。(更新はすでに見た範囲になります。)

②すべての 価値: j について見て行く。後ろから見ていくと、  (v[i],t[i])を取らない推移についても考えることができる。
(一つの時間に対して、最大の価値は一つしか無い)

③(価値 0, 時間 1)という物体があるとすると、dp[m]が最大値と考えることができる。(答えに影響しない)


すごいと思った。

#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int>PA;
using namespace std;
#define MAX  999999
int main(){
	int n,m;
	cin>>n>>m;
	vi v(n),t(n);
	rep(i,n)cin>>v[i]>>t[i];
	vi dp(10000);
	for(int i=0; i<n;i++)
		for(int j=m; j>=0;j--){
			dp[j+t[i]]=max(dp[j+t[i]],dp[j]+v[i]);
		}
	cout<<dp[m]<<endl;
}