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;
}
做法2：DFS
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[110][110];
int dp[110][110][2];
int dfs(int x, int pos){
if(x == n)return a[x][pos];
if(dp[x][pos][0])return dp[x][pos][0];
int maxx = -1e9;
for(int i = pos; i <= m - n + x; i++){
int t = dfs(x + 1, i + 1);
if(maxx < t){
maxx = t;
dp[x][pos][1] = i + 1;
}
}
maxx += a[x][pos];
dp[x][pos][0] = maxx;
return maxx;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
cout << dfs(0, 0) << endl;
int x = 0;
for(int i = 0; i < n; i++){
x = dp[i][x][1];
cout << x << " ";
}
return 0;
}