【动态规划】洛谷2019 OI春令营
【P1464 Function】
【题解】
按照题目意思进行递归即可,但是过程中需要用到记忆化搜索。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll dp[50][50][50]; 5 ll w(ll a,ll b,ll c){ 6 if(a<=0||b<=0||c<=0){return 1;} 7 if(a>20||b>20||c>20){return w(20,20,20);} 8 if(a<b&&b<c){ 9 if(dp[a][b][c-1]==0) dp[a][b][c-1]=w(a,b,c-1); 10 if(dp[a][b-1][c-1]==0) dp[a][b-1][c-1]=w(a,b-1,c-1); 11 if(dp[a][b-1][c]==0) dp[a][b-1][c]=w(a,b-1,c); 12 return dp[a][b][c]=dp[a][b][c-1]+dp[a][b-1][c-1]-dp[a][b-1][c]; 13 }else{ 14 if(dp[a-1][b][c]==0)dp[a-1][b][c]=w(a-1,b,c); 15 if(dp[a-1][b-1][c]==0)dp[a-1][b-1][c]=w(a-1,b-1,c); 16 if(dp[a-1][b][c-1]==0)dp[a-1][b][c-1]=w(a-1,b,c-1); 17 if(dp[a-1][b-1][c-1]==0)dp[a-1][b-1][c-1]=w(a-1,b-1,c-1); 18 return dp[a][b][c] 19 =dp[a-1][b][c] 20 +dp[a-1][b-1][c] 21 +dp[a-1][b][c-1] 22 -dp[a-1][b-1][c-1]; 23 } 24 } 25 int main() 26 { 27 ll a,b,c; 28 while(~scanf("%lld%lld%lld",&a,&b,&c)){ 29 if(a==-1&&b==-1&&c==-1){ 30 break; 31 } 32 ll ans=w(a,b,c); 33 printf("w(%lld, %lld, %lld) = %lld ",a,b,c,ans); 34 } 35 return 0; 36 }
【P1002 过河卒】
【题解】
其实就是马的位置和马口的位置方案为0,无法转移,其他情况照常即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 30 ; 5 ll dp[N][N]; 6 int dir[9][2] = { 7 {-2,-1} , {-2,1}, 8 {-1,-2}, {-1,2}, 9 {0,0}, 10 {1,-2}, {1,2}, 11 {2,-1}, {2,1} 12 }; 13 int main() 14 { 15 int n,m,x,y; 16 cin >> n >> m >> x >> y ; 17 n ++ , m ++ , x ++ , y ++ ; 18 dp[1][1] = 1 ; 19 for(int i=1;i<=n;i++){ 20 for(int j=1;j<=m;j++){ 21 if( i == 1 && j == 1 ) continue ; 22 bool f = true; 23 for(int k=0;k<9;k++){ 24 if( i == x + dir[k][0] && j == y + dir[k][1] ) 25 f = false ; 26 } 27 if( f ) 28 dp[i][j] = dp[i-1][j] + dp[i][j-1]; 29 } 30 } 31 32 printf("%lld ",dp[n][m]); 33 return 0; 34 35 }