版权声明：本文为博主原创文章，未经博主同意不得转载。 https://blog.csdn.net/u012476429/article/details/24798219
- 题意：给两个长度分别为n和m的序列，如今有两种操作：1.分别选择两个序列的一个非空前缀，切两个前缀的最后一位同样，删除之。得到1分（仅仅累计），消耗e；2.直接删除两个序列，消耗值定于两个序列之前删除的元素个数之和，并且使得得到的分有效（之前没有有效分）
(1 ≤ n, m ≤ 105; 1 ≤ s ≤ 3·105; 103 ≤ e ≤ 104)，s代表总能量，e表示一次操作的消耗 - 分析：
首先，问题事实上就是转化成，进行若干次操作1。然后进行操作2
还要找到一个判别标准。来评判较优的状态（贪心）
每次的消耗值比較大，事实上能够计算出最大的删除次数，这个值不是非常大状态表示：
简单的，一个状态能够表示为串A的位置、串B的位置、删除的次数
可是两个串都比較长，假设用串A的位置、串B的位置来作为状态，删除次数作状态值。那么状态集合太大。所以仅仅能以一个串为主串DP，那么删除的次数就应该作为状态，在B的位置应该作为状态的值
操作（状态转移）：
假如对于A的每个位置，都找到一个B中的位置（仅仅有一个选择，必定是找最靠前的）并删除，那么有些状态是遍历不到的，并且非常显然这样的方法是错误的。正确的想法应该是。对于A的每个元素。我们的操作是有两种的，删掉或者不删
判别标准：
每个状态仅仅有一个值，当前串B的位置，看看能否够推断。对于处理到A的同样位置，删除次数同样，那么在B的位置越小越好。能够作为判别标准
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;
}