簡単なDP。5秒考えればわかる。 #include <bits/stdc++.h> using namespace std; #define INF 2000000000 int dp[20010][260]; int c[20],x[20010]; int main(){ int n,m; while(true){ cin >> n >> m; if(n + m == 0)break; for(int i = 0;i < m;i++)cin >> c[i]; for(int </bits/stdc++.h>…

問題文 judge.u-aizu.ac.jp パッと見DP感があるな～と思って少し考えたらほんとにDPだった。 解説： i番目の円とi+1番目の円の交点は2つある。その二つの交点に適当に0個目、1個目の点とすると。 dp[i][j] =0番目の円（一番端の円）から、 i番目の円とi+1番…

解法： 大きめにとった二次元配列に1から10^6までの数の洞穴を書く。（たぶんここが一番めんどくさい エラトステネスで素数をすぐ求められる配列を作っておく。 あとは最初に指定された位置から簡単なDPを解くだけ。（もはやDPと呼べるレベルではない気がす…

パッと見シミュレーションか貪欲法かなと思って考えていたが一向に解法が浮かばなかったので解説を見ました。DPという発想が出てこなかった。こういう問題がでたら確実に通したい。解法： 2個、4個、6個....連続で取り除けるかの情報をdp1[i][j]に保存する。…

イキってDPで解いたら実装重くて痛い目にあった 集中してやったのでバグは起きなかった。dp[i][j][0] : 場所i,jをスタート地点にした時の数字の桁の最大数 dp[i][j][1～] : 最大の時の数字の列これを i = h-1, j = w-1 （一番右下のブロック）から i=0,j=0 …

普通にDPだった。 """IOI列車は闇"""とだけ昔から聞いて怖いなーと思ったけど割と普通に通ってしまった。 闇要素どこにあるんだろう・・・ #include <bits/stdc++.h> using namespace std; int n,m,ans; int s[2004],t[2004]; int dp[2004][2004][2]; int han(int x){ if(x </bits/stdc++.h>…

DP頭悪すぎて謎な漸化式になったがなぜか通った。闇である。以前にも解いてたっぽい 第10回日本情報オリンピック 本選 「古本屋」 AOJ0561 (Books) - intさわだんのBlack History 第10回日本情報オリンピック 本選 「古本屋」 AOJ0561 (Books) - intさわだん…

Solution of this task:DP(dynamic programming).the recurrence formula would be as follows.dp[i][j] := max(dp[i-1][j],dp[i-w][j-1]);dp[i][j] means the maximum achievable score when player threw j balls and knock over no more than i pins.comp…

CCC(Canadian Computing Competition)'s task.This problem is level three (a good grade 12 student MIGHT get this)I used typical DP(Dynamic Programming) to solve this problem. #include <bits/stdc++.h> using namespace std; int dp[30][30]; int r,c,k; bool ch[</bits/stdc++.h>…

なんか前解いたことある気がする。解法：DPコーナーケースがある。 #include <bits/stdc++.h> using namespace std; const int INF = 100000000; int n,ans=-INF,sa[100004][2],am=-INF,dp[100003]; int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++)scanf("%d%d",&sa</bits/stdc++.h>…

DP解説は下を参照してください。 http://www.ioi-jp.org/joi/2013/2014-ho/2014-ho-t2-review.pdf #include <bits/stdc++.h> using namespace std; const int INF = 1000000000; int m,n,ans; int ma[10003]; int ha[503][2]; int dp[503][10003]; int main(){ scanf("%d%d"</bits/stdc++.h>…

DPdp[i][j]:=ジャンルiまでの本をj冊売るときの買い取り価格の最大値.各ジャンルについてソートしてi冊売ったときの値段を記録しておきます。 #include <bits/stdc++.h> using namespace std; int n,dp[2003][2003],b[11][2003],k,co[11]; int main(){ scanf("%d%d",&n,&k);</bits/stdc++.h>…

見るからにDPっぽいDP.N だから恐らくO(N)なんだけど頭が悪いからO(N log N)でといた。dp[i] := i番目の駅に行くときのかかる値段の最小値で求まる。よく読んでいなくて無駄なWAを生やしすぎたし英語力ない。ACしたあと中国人のブログ見てたらみんなO(N)でと…

DPショートコーディング大会みたいになった。 #include <bits/stdc++.h> using namespace std; const int mod = 100000; int w,h,dp[102][102][4]; int main(){ cin >> w >> h; dp[1][1][0] = 1;dp[1][1][3] = 1; for(int i = 1;i <= h;i++){ for(int j = 1;j <= w;j++){ if</bits/stdc++.h>…

ドミノ敷き詰め問題。 完全マッチングの個数を数える問題ともいうのかな。 bitDPでときました。 #include <cstdio> #include <algorithm> #include <string.h> using namespace std; int w,h; long long int dp[2][1 << 11]; int main(){ while(1){ scanf("%d%d",&h,&w); if(h == 0 && w =</string.h></algorithm></cstdio>…

こんな簡単なDPが眠っていたとは。。。 #include <cstdio> #include <algorithm> using namespace std; int p; int s[150002]; int dp[150002][2]; int main(){ scanf("%d",&p); for(int i = 1;i <= p;i++)scanf("%d",&s[i]); for(int i = 1;i <= p;i++){ dp[i][0] = max(dp[i-1</algorithm></cstdio>…

典型DP 予選で出てもおかしくないレベルなので解説は割愛。#include や、using namespace std;は省略することにしました。 const int INF = 1000000000; int n,d; int dp[400][3002][3]; int p[400][3002]; int main(){ scanf("%d%d",&n,&d); for(int i = 0;…

ただのDPのはずかstrlen()多用しすぎててTLEにになっていた。 気をつけよう。 #include <cstdio> #include <string.h> #include <iostream> using namespace std; char a[202],b[202],c[404]; bool dp[202][202]; int main(){ int n; cin >> n; int co = 1; while(n--){ memset(dp, 0, si</iostream></string.h></cstdio>…

個数制限付き部分和問題完全に蟻ゲー詳しくは蟻本p62参照 #include <algorithm> #include <string.h> #include <iostream> #include <cstdio> using namespace std; int a[11]; int m[11]; int dp[100003]; int main(){ int cash; while(cin >> cash){ int n; scanf("%d",&n); for(int i = 0;i < n;i</cstdio></iostream></string.h></algorithm>…

ヤバ問 解説は後ほど #include <cstdio> #include <algorithm> using namespace std; const int INF = 10000000; int n,t[10003]; int dp[2][5101][2]; int main(){ scanf("%d",&n); for(int i = 0;i < n-1;i++){ scanf("%d",&t[i]); } for(int i = 0;i < 2;i++){ for(int j = 0</algorithm></cstdio>…

普通にDPするだけ。 INFがINFになってなくて辛い思いをした。 #include <cstdio> #include <algorithm> #include <string.h> using namespace std; const int INF = 1000000000; int k[153]; int d[153][11][2]; int dp[153][11][80]; int n,m; int main(){ while(1){ scanf("%d%d",&n,&m)</string.h></algorithm></cstdio>…

解法：最長増加部分列(LIS)蟻ゲーです。 #include <cstdio> #include <algorithm> const int INF = 100000000; using namespace std; int main(){ int n; scanf("%d",&n); while(n--){ int p; int d[40003]={0}; int dp[40003] = {0}; scanf("%d",&p); for(int i = 0;i < p;i++)</algorithm></cstdio>…

蟻ゲー以上。 #include <cstdio> #include <string.h> using namespace std; int dp[100003]; int main(){ while(1){ int n,m; int d[102][2]; scanf("%d%d",&n,&m); if(n == 0)break; for(int i = 0;i < n;i++){ scanf("%d",&d[i][0]); } for(int i = 0;i < n;i++){ scanf("%d</string.h></cstdio>…

N年ぶりにDPの問題を解いたけどなんとかできた。。。解法：DP dp[i] = max(dp[i-1],終わる時間がiの中で最も大きいもの);実際問題から計算量O(N)しかありえないっぽいし解法しぼれたのでよかった。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> P</int,int></algorithm></cstdio>…

問題文解法：DP中のDP(?) #include <cstdio> #include <algorithm> using namespace std; int main(){ int t,w,dp[3002][32] = {0}; bool ch[1003]; scanf("%d%d",&t,&w); for(int i = 0;i < t;i++){ int tmp; scanf("%d",&tmp); if(tmp == 1){ ch[i+1] = true; }else{ ch[i+1] </algorithm></cstdio>…

joi-yosen~DP~ #include <cstdio> #include <algorithm> using namespace std; int main(){ int d,n; int kion[203] = {0}; int huku[203][3] = {0}; int dp[203][203] = {0}; scanf("%d%d",&d,&n); for(int i = 0;i < d;i++){ scanf("%d",&kion[i]); } for(int i = 0;i < n;i++</algorithm></cstdio>…

あの有名な最長共通部分列問題。典型的な問題。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int main(){ char a[2000],b[2000]; while(cin>>a>>b){ int dp[1001][1001] = {0}; int alen = strlen(a); int blen = strlen(b); for(int i =</cstring></algorithm></iostream></cstdio>…

JOI予選問題解法:典型的なDP 問題しっかり読もうと思った #include <cstdio> using namespace std; int main(){ const int mod = 10000; int n,k; int yotei[102]={0}; int dp[102][4][2] = {0}; scanf("%d%d",&n,&k); for(int i = 0;i < k;i++){ int a,b; scanf("%d</cstdio>…

問題文解法：DP(上の二つのやつのでかいほうを足していくだけ) #include <cstdio> #include <algorithm> using namespace std; int main(){ int n; int t[102][102] = {0}; int dp[102][102] = {0}; scanf("%d",&n); for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ sca</algorithm></cstdio>…

問題文が中国語⇒英語でさえ読めないのに中国語とかむり。なんとか推測して頑張りました。DPの問題解きたいと思って、簡単そうなのを見つけたのがこれだったが、これはDPと言えるのか❓？？えーと計算量は、O(シラン)ぐらいです（かなり適当なオーダー）なんか…