DPまとめ
40557 ワード
DP使用規則(http://www.cnblogs.com/huangxincheng/archive/2012/02/13/2349664.htmlより抜粋):
①最適化原理(最適サブ構造特性):
1つの問題の最適ポリシーがそのサブ問題のポリシーも最適である場合、この問題は「最適サブ構造特性」と呼ばれる.
②後効性なし:
1つの問題が複数の決定フェーズに分割されると、前のフェーズのポリシーは、後のフェーズのポリシーの影響を受けません.
③サブ問題の重複性:
この性質は動的計画の本質を暴露し,冗長問題を解決し,重複するサブ問題は後段階の決定のために記録することができる.
直接使用することで、アルゴリズムの複雑さを低減します.
解決手順:
①最適解モデルを記述する.
2再帰的定義最適解,すなわち動的計画方程式を構築する.
③底から上への計算最適解.
④最後に計算の最適化に基づいて問題を起こす最適な戦略.
DP照合:
一、01リュック:時間複雑度O(N*V)、NはN個の物品を表し、Vはリュックの重量を表す
for i=1..N
for j=V..0
まず、なぜ01リュックの中でv=V..0の逆順で循環するのかを考えてみましょう.これは、i回目のサイクルにおける状態f[v]が状態f[v−c]から繰返しられることを保証するためである.すなわち、これは、1つのアイテムごとに1回のみ選択されることを保証するためであり、「i番目のアイテムを選択する」という戦略を考慮する際に、i番目のアイテムが選択されていないサブ結果f[v-c]に基づいていることを保証するためである.
二、完全バックパック:O(N*V)個の状態は解く必要があるが、各状態f[v]を解く時間はO(V/c)であり、総複雑度はO(VN)を超える.
for i=1..N
for j=0..V
(http://www.cnblogs.com/shihuajie/archive/2013/04/27/3046458.htmlより抜粋)
初期化の細部の問題私たちが見た最適解を求めるリュックサックの問題の中で、実際には2つの異なる質問法があります.
あるテーマは「リュックサックがちょうどいっぱい入っている」時の最適解を要求し、あるテーマは背中をいっぱい包装しなければならないと要求していない.一つの違い
この2つの質問法の実現方法は,初期化時に異なる.
第1の質問法であれば、リュックサックを適切に満たすことが要求されるが、初期化時にf[0]が0である以外のf[1.V]は-∞に設定され、
これにより,最終的に得られるf[N]がリュックサックを適切に満たす最適解であることが保証される.
バックを満タンにする必要がなく、できるだけ価格を大きくしたい場合は、初期化時にf[0..V]をすべて設定する必要があります.
は0です.
注意:多すぎる賦値演算と呼び出し関数は時間を増加させ、いくつかのBTのテーマに対してif()X=Yという方式を提唱し、X=max(X,Y)を推奨しない.
三、最長共通サブシーケンス
四、経典の数塔問題:
上から下へ、下から上へ、上から下へコードを簡潔に
上-下:
下-上:
五、最大と問題:
1、1次元:
2、2 D:
3、3 D:
N次元に拡張:
六、整数分割:
Cut the rope:長さLのロープを少なくとも2段に分ける異なる長さのロープの案数を解く:
まず,kセグメントに分解すると,nの値は少なくとも1+2+3+4+...+k=(k+1)*k/2
したがって,本題kの最大値は315である.
dp[k][n]がkセグメントとnに分割できるシナリオ数として表されると仮定すると、
状況は2つに分けられます.
1、1つだけのものはdp[k-1][n-k]に等しく、nからk個1を取ってk-1段に分けることができる案数に相当する
2、1がない場合はdp[k][n-k]に等しく、nからk個1を取ってk段に分けることができる案数に相当する
だからdp[k][n]=dp[k-1][n-k]+dp[k][n-k]
七、切漢諾塔のような状態問題を深く浅く解く.
タイトル1:2*1あるいは1*2の骨牌でm*nの碁盤を完全に覆って、カバーする方案の数を求めます:
1、高さ(h)と幅(w)が奇数の場合:
area=h*w;
骨牌面積:2
h*w/2!=0->骨牌で覆わない
2、記f[i][s 1]がi-1行目がフルでi行目がs 1の場合の種数、f[i-1][s 2]がi-2行目がフルでi-1行目がs 2の場合の種数であれば、骨牌のカバー案数はf[h][w<<1-1](h行目がフルである):
結論:i行目の配置シナリオ数は、i-1行目の配置シナリオ数に依存する
各場所について、3つの配置スキームがあります.
1. 縦置き
2. 水平配置
3. 配置しない
dは現在の列番号であり、初期化d,s 1,s 2はいずれも0である.以上の3つの配置方法に対応して、s 1,s 2の調整は:
1. d = d + 1, s1 << 1 | 1, s2 << 1;
2. d = d + 2, s1 << 2 | 3, s2 << 2 | 3;
3. d = d + 1, s1 << 1, s2 << 1 | 1;
まず1つ目の状況について説明し,他の2つの状況は類推できる.
S 1<<1|1は、s 1のバイナリ表示の後に1を付けることであり、本題では(d+1)列に置く
を置き、s 2<<1はs 2のバイナリ表示に0を付けることであり、本題では(d+1)列には置かない.
しかし、なぜs 1、s 2がこのように変化するのでしょうか.s 1は本行の状態に対応し、s 2は前の行の状態に対応し、縦置きできることは前の行の(d+1)列が空いていることを意味するので、このとき前の行の状態はs 2<<1であり、同時に縦置きした後、本行(d+1)行は物を置き、状態はs 1<<1|1となる.
3、初期時のf値は、0行目がフルで、1行目は2つの再生法しかないと仮定することができる.
1. 水平配置d=d+2,s<<2|3; 2. d=d+1,s<<1を置かない;
①最適化原理(最適サブ構造特性):
1つの問題の最適ポリシーがそのサブ問題のポリシーも最適である場合、この問題は「最適サブ構造特性」と呼ばれる.
②後効性なし:
1つの問題が複数の決定フェーズに分割されると、前のフェーズのポリシーは、後のフェーズのポリシーの影響を受けません.
③サブ問題の重複性:
この性質は動的計画の本質を暴露し,冗長問題を解決し,重複するサブ問題は後段階の決定のために記録することができる.
直接使用することで、アルゴリズムの複雑さを低減します.
解決手順:
①最適解モデルを記述する.
2再帰的定義最適解,すなわち動的計画方程式を構築する.
③底から上への計算最適解.
④最後に計算の最適化に基づいて問題を起こす最適な戦略.
DP照合:
一、01リュック:時間複雑度O(N*V)、NはN個の物品を表し、Vはリュックの重量を表す
for i=1..N
for j=V..0
まず、なぜ01リュックの中でv=V..0の逆順で循環するのかを考えてみましょう.これは、i回目のサイクルにおける状態f[v]が状態f[v−c]から繰返しられることを保証するためである.すなわち、これは、1つのアイテムごとに1回のみ選択されることを保証するためであり、「i番目のアイテムを選択する」という戦略を考慮する際に、i番目のアイテムが選択されていないサブ結果f[v-c]に基づいていることを保証するためである.
二、完全バックパック:O(N*V)個の状態は解く必要があるが、各状態f[v]を解く時間はO(V/c)であり、総複雑度はO(VN)を超える.
for i=1..N
for j=0..V
(http://www.cnblogs.com/shihuajie/archive/2013/04/27/3046458.htmlより抜粋)
初期化の細部の問題私たちが見た最適解を求めるリュックサックの問題の中で、実際には2つの異なる質問法があります.
あるテーマは「リュックサックがちょうどいっぱい入っている」時の最適解を要求し、あるテーマは背中をいっぱい包装しなければならないと要求していない.一つの違い
この2つの質問法の実現方法は,初期化時に異なる.
第1の質問法であれば、リュックサックを適切に満たすことが要求されるが、初期化時にf[0]が0である以外のf[1.V]は-∞に設定され、
これにより,最終的に得られるf[N]がリュックサックを適切に満たす最適解であることが保証される.
バックを満タンにする必要がなく、できるだけ価格を大きくしたい場合は、初期化時にf[0..V]をすべて設定する必要があります.
は0です.
注意:多すぎる賦値演算と呼び出し関数は時間を増加させ、いくつかのBTのテーマに対してif()X=Yという方式を提唱し、X=max(X,Y)を推奨しない.
三、最長共通サブシーケンス
int dp[1005][1005];//
char a[1005],b[1005],re[1005][1005];
void dfs(int i,int j)
{
if(i<1||j<1) return;
if(re[i][j]=='c')
{
dfs(i-1,j-1);
cout<<a[i];
}
else dfs(i-(re[i][j]=='x'),j-(re[i][j]=='y'));
}
int main()
{
while(~scanf("%s %s",a+1,b+1))
{
int la=strlen(a+1),lb=strlen(b+1),i,j;
memset(dp,0,sizeof(dp));
//printf("%s
",a+1);
for(i=1;i<=la;++i)
for(j=1;j<=lb;++j)
{
if(a[i]==b[j])
{
dp[i][j]=dp[i-1][j-1]+1;
re[i][j]='c';
}
else {
if(dp[i][j-1]>dp[i-1][j])
{
dp[i][j]=dp[i][j-1];
re[i][j]='y';
}
else{
dp[i][j]=dp[i-1][j];
re[i][j]='x';
}
}
}
printf("%d
",dp[la][lb]);
dfs(la,lb);
printf("
");
}
return 0;
}四、経典の数塔問題:
上から下へ、下から上へ、上から下へコードを簡潔に
上-下:
int dp[105][105];
int main()
{
int n,i,j;
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
for(i=1;i<=n;++i)
for(j=1;j<=i;++j)
{
scanf("%d",&dp[i][j]);
dp[i][j]+=dp[i-1][j-1]>dp[i-1][j]?dp[i-1][j-1]:dp[i-1][j];//important
}
printf("%d
",*max_element(dp[n],dp[n]+n));
}
return 0;
}下-上:
int main()
{
int t,n,a[105][105],i,j;
while(~scanf("%d",&n))
{
for(i=0;i<n;++i)
for(j=0;j<=i;++j)
scanf("%d",&a[i][j]);
for(i=n-1;i>0;--i)
for(j=0;j<i;++j)
{
a[i-1][j]+=a[i][j]>a[i][j+1]?a[i][j]:a[i][j+1];
}
printf("%d
",a[0][0]);
}
return 0;
} 五、最大と問題:
1、1次元:
for(i=0;i<n;++i)
{
scanf("%d",&a);
if(sum<0) sum=a; // 0 , sum
else sum+=a;
Max=sum>Max?sum:Max;
}2、2 D:
for(i=1;i<=r;++i) //r ，c
for(j=0;j<c;++j)
{
scanf("%d",&map[i][j]);
map[i][j]=map[i][j]+map[i-1][j];//
}
for(i=1,m=map[1][0];i<=r;++i) //m
for(j=i;j<=r;++j)
for(k=max=0;k<c;++k)
{
temp=map[j][k]-map[i-1][k];//k ，i j
max=(max>=0?max:0)+temp;// ，max
m=max>m?max:m;//m ，
}
printf("%d
",m);
memset(map,0,sizeof(map));// 3、3 D:
N次元に拡張:
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
void expand(int i,int &b0,int &b1,int &b2)
{
b0=i&1;
i>>=1;
b1=i&1;
i>>=1;
b2=i&1;
}
int sign(int b0,int b1,int b2)
{
return (b0+b1+b2)%2==1?1:-1;
}
const int maxn=30;
const long long INF=1LL<<60;
long long S[maxn][maxn][maxn];
long long sum(int x1,int x2,int y1,int y2,int z1,int z2)
{
int dx=x2-x1+1,dy=y2-y1+1,dz=z2-z1+1;
long long s=0;
for(int i=0;i<8;++i)
{
int b0,b1,b2;
expand(i,b0,b1,b2);
s-=S[x2-b0*dx][y2-b1*by][z2-b2*dz]*sign(b0,b1,b2);
}
return s;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int a,b,c,b0,b1,b2;
scanf("%d%d%d",&a,&b,&c);
memset(S,0,sizeof(S));
FOR(x,1,a)
FOR(y,1,b)
FOR(z,1,c)
scanf("%lld",&S[x][y][z]);
FOR(x,1,a) FOR(y,1,b) FOR(z,1,c) FOR(i,1,7)
{
expand(i,b0,b1,b2);
S[x][y][z]+=S[x-b0][y-b1][z-b2]*sign(b0,b1,b2);
}
long long ans =-INF;
FOR(x1,1,a) FOR(x2,x1,a) FOR(y1,1,b) FOR(y2,y1,b)
{
long long M=0;
FOR(z,1,c)
{
long long s=sum(x1,x2,y1,y2,1,z);
ans=max(ans,s-M);
M=min(M,s);
}
}
printf("%lld
",ans);
if(t) printf("
");
}
return 0;
}六、整数分割:
/*
: n 。
：dp[i][j]: i、 j
dp[i][j] ：1、 j 2、 j
dp[i][j]=dp[i-j][[j]+dp[i][j-1]
： n k 。
dp[n-k][k]： k 1 n ， n-k
： n k 。
dp[n][k]
： n 。
dp1[i][j] i, j ，
dp1[i][j]=dp1[i][i]if(j>i&&j%2==1)
=dp1[i][i-1]if(j>i&&j%2==0)( )
=dp1[i-j][j]+dp1[i][j-2] j ， dp1[i][j-2], dp1[i-j][j];
： n 。
dp2[i][j] ：1、dp1[i][j-1] j 2、dp1[i-j][j-1] j
0-1 ：dp2[i][j]=dp2[i][j-1]+dp2[i-j][j-1]
： n k 。
dp[n][k]: ferrers
24=5+5+5+4+3+2，6 ， 5
24=6+6+5+4+3 5 ， 6
*/
#include <stdio.h>
#define N 52
int dp[N][N] = {0} , dp1[N][N] = {0} , dp2[N][N] = {0} ;
void Divid(){
dp[0][0] = 1 ;
for( int i = 0 ; i < N ; i++ )
for( int j = 1 ; j < N ; j++ ){
if( i < j ) // i<j j i ， 1
dp[i][j] = dp[i][i] ;
else
dp[i][j] = dp[i-j][j] + dp[i][j-1] ;
}
}
void Divid1(){
for( int i = 1 ; i < N ; i++ ) //
dp1[i][1] = 1 ; // 1 ,Answer 1
for( int i = 1 ; i < N ; i+=2 )
dp1[0][i] = 1 ;
dp1[0][0] = 1 ;
for( int i = 1 ; i < N ; i++ )
for( int j = 3 ; j < N ; j+=2 ){ //j
if( j > i ){
if( i&1 )
dp1[i][j] = dp1[i][i] ;
else
dp1[i][j] = dp1[i][i-1] ;
}
else
dp1[i][j] = dp1[i-j][j] + dp1[i][j-2] ;
}
}
void Divid2(){
for( int i = 1 ; i < N ; i++ ){
dp2[0][i] = 1 ;
dp2[1][i] = 1 ;
}
for( int i = 2 ;i < N ; i++ )
for( int j = 1 ;j < N ; j++ ){
if( j > i )
dp2[i][j] = dp2[i][i] ;
else
dp2[i][j] = dp2[i-j][j-1] +dp2[i][j-1] ; //01
}
}
int main(){
int n , k ;
Divid() ;
Divid1() ;
Divid2() ;
while( ~scanf( "%d%d" , &n , &k ) )
{
printf( "%d
" , dp[n][n] ) ; //
printf( "%d
" , dp[n-k][k] ) ; // k
printf( "%d
" , dp[n][k]) ; // k
printf( "%d
" , n&1 ? dp1[n][n] : dp1[n][n-1] ) ; //
printf( "%d
" , dp2[n][n]) ; //
}
return 0;
}Cut the rope:長さLのロープを少なくとも2段に分ける異なる長さのロープの案数を解く:
まず,kセグメントに分解すると,nの値は少なくとも1+2+3+4+...+k=(k+1)*k/2
したがって,本題kの最大値は315である.
dp[k][n]がkセグメントとnに分割できるシナリオ数として表されると仮定すると、
状況は2つに分けられます.
1、1つだけのものはdp[k-1][n-k]に等しく、nからk個1を取ってk-1段に分けることができる案数に相当する
2、1がない場合はdp[k][n-k]に等しく、nからk個1を取ってk段に分けることができる案数に相当する
だからdp[k][n]=dp[k-1][n-k]+dp[k][n-k]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
#define LL long long
#define N 50005
#define mod 1000000
int dp[2][N],sum[N]; //dp
int main()
{
int n,t,i,j,k;
memset(sum,0,sizeof(sum));
/* dp[0] 3 ， 1，
+2， dp[0][i]=dp[0][i-2]+1 */
for(i=3;i<=N;++i) // 3 ，
sum[i]=dp[0][i]=dp[0][i-2]+1;
for(k=3;k<316;++k)
{
int *p1=dp[k&1],*p2=dp[(k+1)&1]; // dp ，
for(i=k*(k+1)/2-1;i>0;i--) p1[i]=0; // ， 0， WA（ 0）
for(i=k*(k+1)/2;i<=N;++i)
{
p1[i]=p1[i-k]+p2[i-k]; //
p1[i]=p1[i]>=mod?p1[i]-mod:p1[i]; // mod
sum[i]+=p1[i];
sum[i]=sum[i]>=mod?sum[i]-mod:sum[i]; // mod
}
}
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d
",sum[n]);
}
return 0;
}七、切漢諾塔のような状態問題を深く浅く解く.
タイトル1:2*1あるいは1*2の骨牌でm*nの碁盤を完全に覆って、カバーする方案の数を求めます:
1、高さ(h)と幅(w)が奇数の場合:
area=h*w;
骨牌面積:2
h*w/2!=0->骨牌で覆わない
2、記f[i][s 1]がi-1行目がフルでi行目がs 1の場合の種数、f[i-1][s 2]がi-2行目がフルでi-1行目がs 2の場合の種数であれば、骨牌のカバー案数はf[h][w<<1-1](h行目がフルである):
結論:i行目の配置シナリオ数は、i-1行目の配置シナリオ数に依存する
各場所について、3つの配置スキームがあります.
1. 縦置き
2. 水平配置
3. 配置しない
dは現在の列番号であり、初期化d,s 1,s 2はいずれも0である.以上の3つの配置方法に対応して、s 1,s 2の調整は:
1. d = d + 1, s1 << 1 | 1, s2 << 1;
2. d = d + 2, s1 << 2 | 3, s2 << 2 | 3;
3. d = d + 1, s1 << 1, s2 << 1 | 1;
まず1つ目の状況について説明し,他の2つの状況は類推できる.
S 1<<1|1は、s 1のバイナリ表示の後に1を付けることであり、本題では(d+1)列に置く
を置き、s 2<<1はs 2のバイナリ表示に0を付けることであり、本題では(d+1)列には置かない.
しかし、なぜs 1、s 2がこのように変化するのでしょうか.s 1は本行の状態に対応し、s 2は前の行の状態に対応し、縦置きできることは前の行の(d+1)列が空いていることを意味するので、このとき前の行の状態はs 2<<1であり、同時に縦置きした後、本行(d+1)行は物を置き、状態はs 1<<1|1となる.
3、初期時のf値は、0行目がフルで、1行目は2つの再生法しかないと仮定することができる.
1. 水平配置d=d+2,s<<2|3; 2. d=d+1,s<<1を置かない;
# include <stdio.h>
# include <string.h>
#include<iostream>
using namespace std;
long long a[2][3000];
int t,n,m;
void dfs(int d,int mm) //d
{
if(d==m)
{
a[0][mm]++;// ， a[0]
return;
}
if(d+1<=m)
dfs(d+1,mm<<1);
if(d+2<=m)
dfs(d+2,mm<<2|3);
}
void DFS(int d,int mm,int nn)//mm ，nn
{
if(d==m)
{
a[t][nn]+=a[(t+1)%2][mm];
return;
}
if(d+1<=m) //
{
DFS(d+1,mm<<1,nn<<1|1); //
DFS(d+1,mm<<1|1,nn<<1); //
}
if(d+2<=m)
DFS(d+2,mm<<2|3,nn<<2|3); //
}
int main()
{
int i;
while(scanf("%d%d",&n,&m)&&n&&m)
{
if((n*m)%2)
{
printf("0
");
continue;
}
if(n>m) // w > h ， ， ， .
n^=m,m^=n,n^=m; // swap(n,m)
memset(a,0,sizeof(a));
dfs(0,0); //
for(i=2;i<=n;i++)
{
t=(i+1)%2;
DFS(0,0,0);
memset(a[(t+1)%2],0,sizeof(a[0]));
}
cout<<a[(n+1)%2][(1<<m)-1]<<endl;
}
return 0;
}