コンテストに参加しなかったのですが、想定解ではない方法で解いたので記事にします。
ABCのD問題、重さを圧縮したらdpで解けるんじゃねと思ってやってるんですが無限にWAを生成してます。なぜ
— yebi (@sigsigma19) 2017年5月2日
解法は,重さの制約が特殊なので最初の重さを引いて動的計画法をします。
個目まで見た時の価値で個選んだときの最大値
として、ナップサックのdpをやります。
多次元DPを初めてやったのですが、良い練習になったと思います。
#include <vector> #include <iostream> #include <utility> #include <algorithm> #include <string> #include <deque> #include <queue> #include <tuple> #include <queue> #include <functional> #include <cmath> #include <iomanip> #include <map> #include <set> #include <numeric> #include <unordered_map> #include <unordered_set> #include <complex> #include <iterator> #include <array> #include <memory> #include <stack> #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 loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; } template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; } #define MAX 9999999 using namespace std; typedef pair<int, int> pii; typedef pair<double,double>pdd; typedef pair<ll,ll>pll; #include<string.h> ll dp[505][105][405]={0}; int main(){ ll N,W; cin>>N>>W; vl v,w; ll lim=0; rep(i,N){ ll value,wegiht; cin>>wegiht>>value; if(wegiht>W)continue; if(!i)lim=wegiht-1; dp[wegiht-lim][i][1]=value; v.push_back(value); w.push_back(wegiht-lim); } for(int j=0;j<N-1;j++){ for(int i=0; i<401;i++){ for(int k=0; k<=N;k++){ if(dp[i][j][k]==0)continue; dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k]); if(i+lim*k+w[j+1]+lim>W)continue; cmax(dp[i+w[j+1]][j+1][k+1],dp[i][j][k]+v[j+1]); } } } ll ans=0; rep(i,401)rep(j,N+1)cmax(ans,dp[i][N-1][j]); cout<<ans<<endl; }