Longest Ordered Subsequence
题解：有两层循环，第二层循环判断第j个位置能不能要[i], 能的话就与当前值比较去max，这需要满足i位置的dp已达最优，所以第一层循环是用来保证每个dp[i]已达最优的。但是没法记录路径，也就是说最大值确实能找到，但是可能有很多路径都满足。题意：有n个数，在保证原有顺序不变的前提下取出尽可能多的数，使得形成的新序列严格递增。输出取出的数个数。
dp[i]：包含第i项，且第i项是最后一个被选中的的最长子序列长度。
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
#define ll long long
const int maxn = 1050;
int n, a[maxn];
ll dp[maxn];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
dp[i] = 1;
}
ll maxx = 0;
//无法记录路径，也就是：最多确实是那么些个，但是到底是那几个点，情况可能有好多
for(int i = 1; i <= n; i ++) {//dp[i]已达最优
for(int j = i + 1; j <= n; j ++) {
if(a[j] > a[i]) {//a[i]能不能选
dp[j] = max(dp[i] + 1, dp[j]);
}
}
maxx = max(maxx, dp[i]);
}
cout << maxx << "\n";
return 0;
}
Super Jumping! Jumping! Jumping!
题意：给定一条长度为n的序列，其中存在一条元素和最大的严格上升子序列，求这条序列的元素和。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1050;
ll a[maxn], dp[maxn];
int main()
{
int n;
while(cin >> n && n) {
for(int i = 1; i <= n; i ++) {
cin >> a[i];
dp[i] = a[i];
}
ll maxx = 0;
for(int i = 1; i <= n; i ++) {
for(int j = i + 1; j <= n; j ++) {
if(a[j] > a[i]) {
dp[j] = max(dp[j], dp[i] + a[j]);
}
}
maxx = max(maxx, dp[i]);
}
cout << maxx << "\n";
}
return 0;
}
Common Subsequence
题意：首先对最长子序列有个定义：如果一个字符串a可以由另一个字符串b删去某些元素得到，那么说明a就是b的子序列字符串。现在有两个字符串，请问最长公共子序列是多长？
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
int main()
{
char s1[maxn], s2[maxn];
while(~scanf("%s%s",s1 + 1, s2 + 1)) {
memset(dp, 0, sizeof(dp));
int l1 = strlen(s1 + 1);
int l2 = strlen(s2 + 1);
for(int i = 1; i <= l1; i ++) {
for(int j = 1; j <= l2; j ++) {
if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
cout << dp[l1][l2] << "\n";
}
return 0;
}
Ignatius and the Princess IV
题意：给出n个数，出题人想找出出现至少(n+1)/2次的数， 现在需要你帮忙找出这个数是多少？
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 20;
int a[maxn], n;
//odd：奇数 出现最多的数 - 其他数总和 >= 1
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
while (cin >> n) {
int sum = 0, ans;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
if (sum == 0) {
sum ++;
ans = a[i];
} else {
if (ans == a[i]) sum ++;
else sum --;
}
}
cout << ans << "\n";
}
return 0;
}
Phalanx
给你一个矩阵，只由小写或大写字母构成。求出它的最大对称子矩阵的边长。其中对称矩阵是一个k*k的矩阵，它的元素关于从左下角到右上角的对角线对称。
题解：dp[i][j]代表以（i，j)为右下角顶点的矩阵中，最大的对称矩阵的边长。每次dp[i][j]都以dp[i-1][j-1]为参考，只遍历一行一列，且遍历的k值小于dp[i-1][j-1]。
初始化：dp[i][j] = 1
需要注意的是，当遇到不满足对称条件的两个顶点时，循环结束。但这并不意味着dp[i][j]只能等于1，它的值应该是遍历结束时f的值 + 1。
#include<bits/stdc++.h>
using namespace std;
#define TLE std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int maxn = 1050;
char a[maxn][maxn];
int n;
int dp[maxn][maxn];
int main() {
TLE;
while (cin >> n && n) {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
dp[i][j] = 1;
}
}
for (int i = n; i >= 1; i --) {
for (int j = 1; j <= n; j ++) {
cin >> a[i][j];
}
}
int maxx = 1;
for (int i = 2; i <= n; i ++) {
for (int j = 2; j <= n; j ++) {
int f = 0;
int t = dp[i - 1][j - 1];
for (int k = 1; k <= t; k ++) {
if (a[i - k][j] != a[i][j - k]) {//写成dp了
break;
}
f ++;
}
if (f) {
dp[i][j] += f;
}
maxx = max(maxx, dp[i][j]);
}
}
cout << maxx << "\n";
}
return 0;
}
标签：std,maxx,12,int,maxn,DP,kuangbin,include,dp From： https://www.cnblogs.com/coding-inspirations/p/16722131.html