首页 > 代码库 > Codeforces Round #244 (Div. 2)——Match & Catch
Codeforces Round #244 (Div. 2)——Match & Catch
题目链接
- 题意:给两个长度分别为n和m的序列,现在有两种操作:1.分别选择两个序列的一个非空前缀,切两个前缀的最后一位相同,删除之,得到1分(只累计),消耗e;2.直接删除两个序列,消耗值定于两个序列之前删除的元素个数之和,并且使得得到的分有效(之前没有有效分)
- 分析:
首先,问题其实就是转化成,进行若干次操作1,然后进行操作2
还要找到一个判别标准,来评判较优的状态(贪心)
每次的消耗值比较大,其实可以计算出最大的删除次数,这个值不是很大
状态表示:
简单的,一个状态可以表示为串A的位置、串B的位置、删除的次数
但是两个串都比较长,如果用串A的位置、串B的位置来作为状态,删除次数作状态值,那么状态集合太大。所以只能以一个串为主串DP,那么删除的次数就应该作为状态,在B的位置应该作为状态的值
操作(状态转移):
假如对于A的每一个位置,都找到一个B中的位置(只有一个选择,必然是找最靠前的)并删除,那么有些状态是遍历不到的,而且很显然这种方法是错误的。正确的想法应该是,对于A的每一个元素,两种操作:删除或者不删除
判别标准:
每个状态只有一个值,当前串B的位置,看看是否可以判断;对于处理到A的相同位置,删除次数相同,那么在B的位置越小越好。可以作为判别标准
显然,这个时候是存在贪心的。其实想一想,对于之前见到的DP,对于DP状态的合并其实也是基于贪心原理(距离最小,价值最小等等),有时候能找到贪心也就基本找到了DP的判别标准(进行状态合并)
const int MAXN = 100001; int ipta[MAXN], iptb[MAXN]; int dp[2][310]; vector<int> vt[MAXN]; int main() { // freopen("in.txt", "r", stdin); int a, b, all, c, cnt; while (~RIV(a, b, all, c)) { int cur = 0; CLR(dp, INF); REP(i, MAXN) vt[i].clear(); cnt = (all + c - 1) / c; FE(i, 1, a) RI(ipta[i]); FE(i, 1, b) { RI(iptb[i]); vt[iptb[i]].push_back(i); } int ans = 0; FE(i, 1, a) { dp[cur][0] = 0; cur ^= 1; CLR(dp[cur], INF); FE(j, 1, cnt) { int pre = dp[cur ^ 1][j - 1]; int p = upper_bound(all(vt[ipta[i]]), pre) - vt[ipta[i]].begin(); if (p == vt[ipta[i]].size()) p = INF; else p = vt[ipta[i]][p]; dp[cur][j] = min(dp[cur ^ 1][j], p); if (dp[cur ^ 1][j] > p && p + i + j * c <= all) ans = max(ans, j); } } WI(ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。