• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

codeforces425C

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题意:给定长度为n,m<=100000的范围在100000以内的数组a,b。

        现在给定两种操作:

              第一种是ai,bj相等,ai,bj之前的数全删掉,费用为e,收益为1

              第二种是把剩下的全部删掉,花费为之前删除的数的个数,并且得到的之前的收益(也就是必须这一步,不然1的收益都无效)

思路:刚开始看错题意了。。以为第二种操作花费为剩下的个数。。

        然后多写了一段。。。还wa了。。虽然思路差不多。。

        那么题目等价与a,b数组中找到最多的不相交线段。。

        但是单纯这样还是要跪。。注意到s/e<=300,那么就可以二维dp

         f[i][j]表示做到a[i],有j对不相交线段的最近额b数组出现在什么位置。。

         那么做法就很像不下降子序列nlogn版本的做法了。。

          具体看代码吧。。

code:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define vii vector<int>::iterator
 4 #define M0(a) memset(a, 0, sizeof(a))
 5 #define repf(i, a, b) for (int i = (a); i <= (b); ++i) 
 6 int a[101010], b[101010], n, m, s, e;
 7 int f[301];
 8 vector<int> p[101010];
 9 
10 void init(){
11     repf(i, 1, n) scanf("%d", &a[i]);
12     repf(i, 1, m) scanf("%d", &b[i]);
13     for (int i = 0; i <= 100000; ++i) p[i].clear();
14     repf(i, 1, m) p[b[i]].push_back(i);
15 }
16 
17 void solve(){
18     int t = s / e;
19 //    cout << t << endl;
20     for (int i = 0; i <= t; ++i) f[i] = m+1;
21     f[0] = 0;
22     int ans = 0;
23     for (int i = 0; i < n; ++i){
24         for (int j = t; j >= 0; --j) if (f[j] <= m){
25                vii it = upper_bound(p[a[i+1]].begin(), p[a[i+1]].end(), f[j]);
26                if (it != p[a[i+1]].end()) f[j+1] = min(f[j+1], *it);
27         }
28         for (int j = 0; j <= t; ++j) if (f[j] <= m)
29              if (j * e + f[j] + i + 1 <= s) ans = max(ans, j);    
30     }
31     cout << ans << endl;
32 }
33 
34 int main(){
35 //    freopen("a.in", "r", stdin);
36     while (scanf("%d%d%d%d", &n, &m, &s, &e) != EOF){
37           init();
38           solve();
39     }
40 }
View Code

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Objective-C@property发布时间:2022-07-13
下一篇:
C#.netCoreWebApi系列(一)创建与使用发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap