dp题目集合

1.Problem - 2B - Codeforces 

最终有几个零，是有乘积中2,5因数个数的最小值决定的。所以这里a,b分别待办2,5,的最少。

#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> PII;
#define pb emplace_back
//#define int ll
#define all(a) a.begin(),a.end()
#define x first
#define y second
#define ps push_back
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)void solve();const int N = 1e3 + 10;signed main() {IOS;ll t = 1;while (t--)solve();return 0;
}ll dp[N][N][2];
ll path[N][N][2];
ll a[N][N],b[N][N];void dfs(ll x, ll y, ll k)
{if(x == 1 && y == 1) return;//endif(path[x][y][k]){dfs(x,y-1,k); cout << "R";}else{dfs(x-1,y,k);cout << "D";}
}void solve() {ll n; cin >> n;ll flag = 0;for(int i = 1; i <= n; ++ i)for(int j = 1; j <= n; ++ j){ll x; cin >> x;if(x == 0) x = 10, flag = i;while(x % 2 == 0) x >>= 1, a[i][j] ++;while(x % 5 == 0) x /= 5, b[i][j] ++;}memset(dp,0x3f,sizeof(dp));dp[1][1][0] = a[1][1], dp[1][1][1] = b[1][1];//0 : 2     1 : 5for(int i = 1; i <= n; ++ i){for(int j = (i == 1) ? 2 : 1; j <= n; ++ j){if(dp[i-1][j][0]<=dp[i][j-1][0]){path[i][j][0]=0;}else path[i][j][0]=1;if(dp[i-1][j][1]<=dp[i][j-1][1]){path[i][j][1]=0;}else path[i][j][1]=1;dp[i][j][0]=min(dp[i-1][j][0],dp[i][j-1][0])+a[i][j];dp[i][j][1]=min(dp[i-1][j][1],dp[i][j-1][1])+b[i][j];}}ll k;if(dp[n][n][0] < dp[n][n][1])k = 0;//2 ...else k = 1;if(flag && dp[n][n][k]){cout << 1 << endl;for(int i = 1; i < flag; ++ i) cout << "D";for(int i = 1; i < n; ++ i) cout << "R";for(int i = flag; i < n; ++ i) cout << "D";}else{cout << dp[n][n][k] << endl;dfs(n,n,k);}
}