kurarrr's memooo

主に競プロ備忘録

蟻本練習問題(DP)

競プロ

基本的な動的計画法

問題訳(かなり意訳)

N(1\leq N \leq 350) 列に1,2,...,N個ずつ三角形でボーリングのピンが並んでいる。
ボーリングのピンには点数 K(0 \leq K \leq 99) がついていて、ボールは三角形の一番上から下の二つの隣接するピンを倒すことができ、一番下に向けて動く。
得られる最大の点数は何点か。

ex.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

この場合だと 7 -> 3 -> 8 -> 7 -> 5 で30点が最高点。

解法
かなりわかりやすいDP。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=351;

int dp[MAX_N][MAX_N],a[MAX_N][MAX_N];

int main(){
  int N;
  cin >> N ;
  rep(i,N){
    rep(j,i+1) scanf("%d",&a[i][j]);
  }
  fill(dp[0],dp[MAX_N-1],-1);
  dp[0][0]=a[0][0];
  rep(i,N-1){
    rep(j,i+1){
      dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a[i+1][j]);
      dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+a[i+1][j+1]);
    }
  }
  int ans=-1;
  rep(i,N) ans=max(ans,dp[N-1][i]);
  cout << ans << endl;
  return 0;
}

問題訳
自然数 N(1\leq N \leq 10^{6}) が与えられる。
Nを 2^{k} (k \geq 0) の和だけで表す方法は何通りあるか。

解法 まず書き出してみる。
1=1 ...1
2=2=1+1 ...2
3=1+2,1+1+1 ...2
4=4=2+2=1+1+2=1+1+1+1 ...4
5=1+(4の表し方) ...4
Nの組み合わせ数をdp[N]とすれば、N=奇数の時 dp[N]=dp[N-1]は容易に得られる。
なぜならNは奇数であるため、和で表した時少なくとも1つ、1が入るためである。
一方、Nが偶数であれば1を一つも使わずに表すことができるため、これは成り立たない。
しかし、その時は分解した和が全て偶数だからN/2を和で表したものを2倍したものと考えることができる。 よって、

$$ dp[n]=\begin{cases} dp[n-1] & (n=odd) \\ dp[n-1] + dp[n/2] & (n=even) \end{cases} $$

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=1e7;

ll dp[MAX_N];

int main(){
  int N;
  cin >> N ;
  dp[1]=1;
  REP(i,2,N+1){
    if(i%2) dp[i]=dp[i-1]%int(mod);
    else dp[i]=(dp[i/2]+dp[i-1])%int(mod);
  }
  cout << dp[N] << endl;
  return 0;
}

問題訳
毎秒、木1と木2のどちらかからりんごが落ちてくる。牛のベシーは木の真下にいればりんごをキャッチすることができる。
最大移動回数W(1\leq W \leq 30)回の元で、T(1\leq T \leq 1000)秒間の間に最大何個のりんごを得られるか。

解法
i秒後、j回移動して得られる最大のりんごの数をdp[i][j]とする。
今どちらかにいるかは j%2 +1 で得られる。 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])と、
今いる場所に落ちてくるなら dp[i][j]++ を繰り返せば答えが得られる。
木をN本に拡張してもできそう。その場合はjは今いる木の場所になるのかな。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_T=1002,MAX_W=31;

int dp[MAX_T][MAX_W];

int main(){
  int T,W;
  cin >> T >> W ;
  fill(dp[0],dp[T+1],0);
  REP(i,1,T+1){
    int fall;
    cin >> fall ;
    rep(j,W+1){ 
      if(j>0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
      else dp[i][j]=dp[i-1][j];
      int now = j%2+1;
      if(now==fall) dp[i][j]++;
    }
  }
  int ans=-1;
  rep(j,W+1) ans=max(ans,dp[T][j]);
  cout << ans << endl;
  return 0;
}

問題訳 次のN時間で最大の牛乳を得られるようにしたい。
搾乳することができる時間はM区間あり、それぞれでs_iからe_iまで時間がかかり、effi_iだけ牛乳が得られる。
また、牛は一回搾乳をするごとにR時間休ませる必要がある。(つまりi個目の区間で搾乳をするとe_i+Rから搾乳を再開できる)

入力
N M R
s_1 e_1 effi_1
. .
s_M e_M effi_M

$$ 1\leq R \leq N \leq 10^{6}
1 \leq M \leq 10^{3}
1 \leq s_i \leq e_i \leq N
1 \leq effi_i \leq 10^{6}
$$

解法 各区間を開始時間でソートする。
区間に関するDPを立てて解く。
dp[i] := (i番目以降の区間を用いた場合の最大搾乳量)とする。
i番目の区間で搾乳をしないとすると、dp[i+1]だけ搾乳できる。
搾乳をするならば、開始時間がe_i+R以上になるような最小の数をj\leq iとすれば、
dp[j]+effi_i だけ搾乳することができる。そのようなjは二分探索で発見できる。
よって dp[i]=max(dp[i+1],dp[j]+effi_i)
求める答えはdp[0]
計算時間は検索で二分探索を用いているのでO(MlogM)。 M〜103なので二分探索を用いなくても間に合う。

メモ
何に関するDPを立てるのかパッと思いつかなかった。Nでやるとちょっと怖そうだしなーと。
Nに関するDPでもできるっぽい
POJ-3616 : Milking Time
後ろからやるの、思いつかない。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_M=1002;

vector<pair<P,ll>> term;
ll dp[MAX_M];

int main(){
  int N,M,R;
  cin >> N >> M >> R ;
  term.resize(M);
  rep(i,M){
    int s,e;
    ll ef;
    scanf("%d%d%lld",&s,&e,&ef);
    term[i].first.first = s;
    term[i].first.second = e;
    term[i].second = ef;
  }
  sort(ALL(term));
  dp[M-1] = term[M-1].second;
  for(int i=M-2;i>=0;i--){
    pair<P,ll> temp;
    temp.first.first = term[i].first.second+R;
    temp.first.second = -1;
    int _m = lower_bound(term.begin(),term.end(),temp) - term.begin();
    if(_m==M) dp[i] = max(dp[i+1],term[i].second);
    else dp[i] = max(dp[i+1],dp[_m]+term[i].second);
  }
  cout << dp[0] << endl;

  return 0;
}
  • POJ3280 – Cheapest Palindrome
    N種類のアルファベットからなるM字の文字列が与えられる。
    各アルファベットの追加と削除のコストが与えられた時、文字列を回文にするためのコストを求めよ。
    input
    N M
    S(M文字の文字列)
    a (aを追加するコスト) (aを削除するコスト)
    ...
    (M番目のアルファベット) (追加するコスト) (削除するコスト)
    1 \leq N \leq 26 , 1 \leq M \leq 2*10^{3}, 1\leq cost \leq 10^{4}

解法
区間DP。
dp[i][j] := [i,j)を回文にするコストとする。
すると
S[i] = S[j-1] のとき S[i][j] = min(dp[i][j-1] + cost[S[j-1]] , dp[i+1][j] + cost[S[i]] , dp[i+1][j-1])
そうでないとき S[i][j] = min(dp[i][j-1] + cost[S[j-1]] , dp[i+1][j] + cost[S[i]] )
である。これを(i,j) = (0,2),(1,3),..,(M-2,M), (0,3),...,(M-3,M),...,(0,M)と回していけば良い。
dp[i][i+1] = 0 (1文字でもともと回文のため)
求める答えは dp[0][M]。計算量はO(M2)

メモ
区間DPの書き方が慣れない。あとうまい書き方が知りたい。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60,lmod=1e9+7;
const int MAX_N=2003;

ll dp[MAX_N][MAX_N];
map<char,ll> cost;

int main(){
  int N,M;
  cin >> N >> M ;
  string S;
  cin >> S ;
  rep(i,N){
    char c;
    ll a,b;
    cin >> c >> a >> b ;
    cost[c] = min(a,b);
  }
  fill(dp[0],dp[MAX_N-1],0);
  REP(j,2,M+2) REP(i,0,M-j+2) {
    ll temp = min(dp[i][i+j-1]+cost[S[i+j-1]],dp[i+1][i+j]+cost[S[i]]);
    if(S[i]==S[i+j-1]) dp[i][i+j] = min(temp,dp[i+1][i+j-1]);
    else dp[i][i+j] = temp;
    //cout << i << ","<< i+j << ":" << dp[i][i+j] << endl;
  }
  cout << dp[0][M] << endl;
  return 0;
}

参考
基本的な動的計画法(5題)
大いに参考にさせていただきました...