中介专门做别墅的网站,杭州网站优化效果,主流的网站建设的软件,wordpress调用评论代码前两题一直在打模拟赛#xff0c;有点忙#xff0c;就没更
Red Playing Cards 算法#xff1a;动态规划
其实这就是一个线段覆盖问题#xff0c;只不过大线段能够包含小线段。 这就启发我们#xff0c;对于每个大线段分别跑一个dp#xff0c;合并在他内部的小线段。而后…前两题一直在打模拟赛有点忙就没更
Red Playing Cards 算法动态规划
其实这就是一个线段覆盖问题只不过大线段能够包含小线段。 这就启发我们对于每个大线段分别跑一个dp合并在他内部的小线段。而后对于每一个大线段再跑一个总的dp即可。
也可以只跑一遍dp有一个小trick在线段两端添0这样答案就等同于f[0]
#includebits/stdc.h
using namespace std;#define int long longconst int N 6e3100;
int n;
int f[N];
int l[N],r[N];
int a[N];struct Node{int l,r,x;
}b[N];int g[N];
int dp[N];bool cmp(Node x,Node y){int l1 x.r-x.l1;int l2 y.r-y.l1;return l1 l2;
}signed main(){cinn;for (int i 1; i 2*n; i){cina[i];if (l[a[i]] 0) l[a[i]] i;else r[a[i]] i;}for (int i 1; i n; i)b[i] {l[i],r[i],i};sort(b1,bn1,cmp);for (int i 1; i n; i){int x b[i].x;for (int j 1; j 2*n; j) g[j] 0;for (int j b[i].l; j b[i].r; j){g[j] g[j-1]x;if (l[a[j]] j l[a[j]] b[i].l)g[j] max(g[l[a[j]]-1]f[a[j]],g[j]);}f[x] g[b[i].r];}for (int i 1; i 2*n; i){dp[i] max(dp[i-1],dp[i]);if (l[a[i]] i) continue;dp[i] max(dp[i],dp[l[a[i]]-1]f[a[i]]);}coutdp[2*n];return 0;
}#includebits/stdc.h
using namespace std;#define int long longconst int N 6e3100;
int n;
int f[N];
int l[N],r[N];
int a[N];struct Node{int l,r,x;
}b[N];int g[N];
int dp[N];bool cmp(Node x,Node y){int l1 x.r-x.l1;int l2 y.r-y.l1;return l1 l2;
}signed main(){cinn;for (int i 2; i 2*n1; i){cina[i];if (l[a[i]] 0) l[a[i]] i;else r[a[i]] i;}for (int i 1; i n; i)b[i] {l[i],r[i],i};b[n1] {1,2*n2,0}; n;sort(b1,bn1,cmp);for (int i 1; i n; i){int x b[i].x;for (int j 0; j 2*n; j) g[j] 0;for (int j b[i].l; j b[i].r; j){g[j] g[j-1]x;if (l[a[j]] j l[a[j]] b[i].l)g[j] max(g[l[a[j]]-1]f[a[j]],g[j]);}f[x] g[b[i].r];}coutf[0];
// for (int i 1; i 2*n; i){
// dp[i] max(dp[i-1],dp[i]);
// if (l[a[i]] i) continue;
// dp[i] max(dp[i],dp[l[a[i]]-1]f[a[i]]);
// }
// coutdp[2*n];
// for (int i 1; i n; i) couti f[i]endl;return 0;
}Lucky Common Subsequence 算法KMPdp
这题只是一个加强版的LCS只不过多了一个子串的限定。 所以我们不难想到状态设置: f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示第一个串从1……i第二个串从2……j匹配了第三个串k个长度的最长LCS 关键就是第三维状态的转移我们不能随便转移而是利用KMP的NEXT数组进行转移 在第三个串的k位之后加入s[i]利用NEXT数组转移到相应的位置进行转移。 由于本题要求输出路径有两种方法 第一种就是常规的求最长长度而后利用状态关系倒序递归输出。 第二种就是直接用string去存储答案。 这里用的第二种方法
#includebits/stdc.h
using namespace std;const int N 1e210;
string f[N][N][N];
int n,m,q;
char s1[N],s2[N],s3[N];
int Ne[N];void KMP(){Ne[1] 0;int j 0;for (int i 2; i q; i){while (j 0 s3[i]!s3[j1]) jNe[j];if (s3[i] s3[j1]) j;Ne[i] j;}
}void Com(string a,string b){if (a.size() b.size()) a b;
}int main(){cin(s11); cin(s21); cin(s31);n strlen(s11); m strlen(s21); q strlen(s31);KMP();for (int i 1; i n; i){for (int j 1; j m; j){for (int k 0; k q; k){Com(f[i][j][k],f[i-1][j][k]);Com(f[i][j][k],f[i][j-1][k]);if (s1[i]!s2[j]) continue;int now k;while (now s1[i]!s3[now1]) now Ne[now];if (s1[i] s3[now1]) now;Com(f[i][j][now],f[i-1][j-1][k]s1[i]);}}}string ans ;for (int i 0; i q; i)Com(ans,f[n][m][i]);if (ans.size() 0) cout0; else coutans;return 0;
}算是一个比较典的KMPdp的题目
