5.8线性动态规划2

P1004 [NOIP 2000 提高组] 方格取数

做法1：DFS+剪枝

#include<bits/stdc++.h>
using namespace std;
int n, a[10][10], maxs, minx = 11, miny = 11, maxx, maxy;
void dfs(int x, int y, int s, int type){if(type == 1 && x == minx && y == miny){maxs = max(maxs, s);return;}else if(x < minx || x > maxx || y < miny || y > maxy)return;else if(x == maxx && y == maxy)type = 1;int z = a[x][y];a[x][y] = 0;if(type){dfs(x - 1, y, s + z, type);dfs(x, y - 1, s + z, type);}else{dfs(x + 1, y, s + z, type);dfs(x, y + 1, s + z, type); }a[x][y] = z;
}
void solve(){cin >> n;int x, y, v;while(cin >> x >> y >> v, x || y || v){a[x][y] = v;minx = min(minx, x);miny = min(miny, y);maxx = max(maxx, x);maxy = max(maxy, y);}dfs(minx, miny, 0, 0);cout << maxs << endl;
} 
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

做法2：动态规划

四维数组

#include<bits/stdc++.h>
using namespace std;
int a[12][12], dp[12][12][12][12]; 
int mmax(int a, int b, int c, int d){return max(max(a, b), max(c, d));
}
void solve(){int n, x, y, s;cin >> n;while(cin >> x >> y >> s)a[x][y] = s;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){for(int k = 1; k <= n; k++){for(int l = 1; l <= n; l++){if(i + j == k + l){dp[i][j][k][l] = mmax(dp[i - 1][j][k - 1][l], dp[i - 1][j][k][l - 1], dp[i][j - 1][k - 1][l], dp[i][j - 1][k][l - 1])+ a[i][j] + a[k][l];if(i == k && j == l) dp[i][j][k][l] -= a[k][l];}}}}}cout << dp[n][n][n][n] << endl;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

P4933 大师

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010; int mod = 998244353;
int a[N], f[N][N];
int ans;
void solve(){int n; cin >> n;int flag = 0;int temp = 0;for(int i = 1; i <= n; i++){cin >> a[i];if(i == 1)temp = a[i];else{if(temp != a[i])flag = 1;}}if(flag == 0){long long sum = 1;for(int i = 1; i <= n; i++){sum = (sum * 2) % mod;}cout << (sum - 1 + mod) % mod << endl;return;}ans += n;for(int i = 1; i < n; i++){for(int j = i + 1; j <= n; j++){f[i][j] = 1;int x = a[j] - a[i];for(int k = 1; k < i; k++){if(x == a[i] - a[k]){f[i][j] = (f[i][j] + f[k][i]) % mod;}}ans = (ans + f[i][j]) % mod;}}cout << ans << endl;
} 
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

P1435 [IOI 2000] 回文字串

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
void solve(){cin >> a + 1;int len = strlen(a + 1);for(int i = 1; i <= len; i++){b[len - i + 1] = a[i];}for(int i = 1; i <= len; i++){for(int j = 1; j <= len; j++){if(a[i] == b[j])f[i][j] = f[i - 1][j - 1] + 1;else f[i][j] = max(f[i - 1][j], f[i][j - 1]);}}cout << len - f[len][len] << endl;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

P1439 【模板】最长公共子序列

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], b[N];
map<int, int> mp;
set<int> se;
void solve(){int n; cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];mp[a[i]] = i;}for(int i = 1; i <= n; i++)cin >> b[i];se.insert(mp[b[1]]);for(int i = 2; i <= n; i++){auto it = se.lower_bound(mp[b[i]]);if(it != se.end())se.erase(it);se.insert(mp[b[i]]);}cout << se.size() << endl;
} 
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

 下面是手搓二分

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], b[N], f[N], mp[N];void solve(){int n; cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];mp[a[i]] = i;}for(int i = 1; i <= n; i++)cin >> b[i];f[0] = 0;int len = 0;for(int i = 1; i <= n; i++){if(mp[b[i]] > f[len])f[++len] = mp[b[i]];int l = 0, r = len + 1;while(l + 1 != r){int mid = l + r >> 1;if(mp[b[i]] > f[mid])l = mid;else r = mid;}f[r] = min(f[r], mp[b[i]]);}cout << len << endl;
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

P2679 [NOIP 2015 提高组] 子串

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod = 1e9 + 7;
int dp[2][210][210][2];
void solve(){int n, m, k; cin >> n >> m >> k;string s1, s2; cin >> s1 >> s2;s1 = " " + s1, s2 = " " + s2;for(int i = 0; i <= 2; i++)dp[i][0][0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){for(int l = 1; l <= k; l++){dp[1][j][l][0] = (dp[0][j][l][0] + dp[0][j][l][1]) % mod;if(s1[i] == s2[j]){dp[1][j][l][1] = (dp[0][j - 1][l][1] + dp[0][j - 1][l - 1][1] + dp[0][j - 1][l - 1][0]) % mod;}else{dp[1][j][l][1] = 0;}}}memcpy(dp[0], dp[1], sizeof(dp[1]));}cout << (dp[1][m][k][0] + dp[1][m][k][1]) % mod << endl;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

P1854 花店橱窗布置

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N][N][2];
void dfs(int n, int pos){if(n == 1)return;int x = a[n][pos][1];dfs(n - 1, x);cout << x << " ";
}
void solve(){int n, m; cin >> n >> m;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> a[i][j][0];}}int maxs, maxpos = 0;for(int i = 2; i <= n; i++){maxs = -1e9;for(int j = i - 1; j <= i - 1 + m - n; j++){if(a[i - 1][j][0] > maxs){maxs = a[i - 1][j][0];maxpos = j;}a[i][j + 1][0] += maxs;a[i][j + 1][1] = maxpos;}}maxs = -1e9;for(int i = n; i <= m; i++){if(a[n][i][0] > maxs){maxs = a[n][i][0];maxpos = i;}}cout << maxs << endl;dfs(n, maxpos);cout << maxpos << endl;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}