题目链接：5693

题目链接：5712

对于这个D game。注意消除之后两遍的序列是可以拼合到一起的！我们可以想到有区间DP的做法。我们设\(f[i][j]\)表示区间i,j可以被消除。

显然如果这个区间可以被消除，则操作一定可以被分解成一次消除两个k1次，一次消除三个k2次。所以我们只考虑消除两个和消除三个的情况即可。

开始可以把公差放进set里面，方便之后查询。

具体转移见代码。

处理完哪些区间可以被消除之后，我们可以利用贪心来计算最大消除的数量。（要先把可行区间放入到一个vector里面，然后排序，按照长度为第一关键字，左端点为第二关键字。因为大区间一定覆盖它里面的小区间，所以我们只要遇到自己区间已经被计算过了就不用计算这整个区间了）。

代码如下：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<set>

#include<vector>

#define MAXN 310

using namespace std;

int t,n,m,cur,ans;

struct Edge{int l,r,dis;};

int a[MAXN],f[MAXN][MAXN],done[MAXN],dp[MAXN];

set<int>s;

vector<Edge>v;

inline bool cmp(struct Edge x,struct Edge y)

{

    if(x.dis==y.dis) return x.l<y.l;

    return x.dis>y.dis;

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("ce.in","r",stdin);

    #endif

    scanf("%d",&t);

    while(t--)

    {

        ans=0;

        s.clear();v.clear();

        memset(f,0,sizeof(f));

        memset(done,0,sizeof(done));

        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i][i-1]=1;

        for(int i=1;i<=m;i++) scanf("%d",&cur),s.insert(cur);

        for(int i=1;i<=n;i++)

        {

            for(int l=1;l+i<=n;l++)

            {

                int r=l+i;

                //printf("l=%d r=%d\n",l,r);

                if(f[l+1][r-1]&&s.count(a[r]-a[l])) f[l][r]=1;

                if(!f[l][r])

                {

                    for(int k=l+1;k<=r-1;k++)

                    {

                        int cha1=a[r]-a[k],cha2=a[k]-a[l];

                        if((f[l][k-1]&&f[k][r])||(f[l+1][k-1]&&f[k+1][r-1]&&cha1==cha2&&s.count(cha1)))

                            {f[l][r]=1;break;}

                    }

                }

            }

        }

        for(int i=1;i<=n-1;i++)

            for(int j=i+1;j<=n;j++)

                if(f[i][j])

                    v.push_back((Edge){i,j,j-i+1});

        sort(v.begin(),v.end(),cmp);

        int cur=0;

        for(int i=0;i<v.size();i++)

        {

            bool flag=true;

            for(int j=v[i].l;j<=v[i].r;j++)

                if(done[j]==1)

                    {flag=false;break;}

            if(flag==false) continue;

            for(int j=v[i].l;j<=v[i].r;j++)

                done[j]=1;

        }

        for(int i=1;i<=n;i++) if(done[i]) ans++;

        printf("%d\n",ans);

    }

    return 0;

}

然后对于那个加强版。

我想的是因为它的公差的种类数量很少，所以我想的是直接记录一下哪个区间里面有多少种公差，那么就知道了消除这个区间至少需要多少次。但是这样的话没有办法判断一次消除到底有没有满足消除数量在min,max范围内。。。。

所以说这个题我还木有A掉。。。。但是在网上也没有找到题解。。。。就先把自己WA的代码放在这里好了。。。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<set>

#include<vector>

#include<map>

#define MAXN 100

using namespace std;

int t,n,m,cur,ans,minn,maxx,cnt,kkk;

struct Edge{int l,r,dis;};

struct Node{int sum[40];}node[MAXN][MAXN];

int a[MAXN],f[MAXN][MAXN],done[MAXN],dp[MAXN];

set<int>s;

vector<Edge>v;

map<int,int>id;

inline bool cmp(struct Edge x,struct Edge y)

{

    if(x.dis==y.dis) return x.l<y.l;

    return x.dis>y.dis;

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("ce.in","r",stdin);

    #endif

    scanf("%d",&t);

    while(t--)

    {

        kkk++;

        ans=cnt=0;

        s.clear();v.clear();

        memset(f,0,sizeof(f));

        memset(done,0,sizeof(done));

        scanf("%d%d%d%d",&n,&m,&minn,&maxx);

        for(int i=1;i<=n;i++) scanf("%d",&a[i]);

        for(int i=1;i<=m;i++) scanf("%d",&cur),s.insert(cur),id[cur]=i;

        for(int i=1;i<=n;i++)

        {

            f[i][i-1]=1;

            if(s.count(a[i+1]-a[i]))

                node[i][i-1].sum[id[a[i+1]-a[i]]]=1;

        }

        for(int i=1;i<=n;i++)

        {

            for(int l=1;l+i<=n;l++)

            {

                int r=l+i;

                if(f[l+1][r-1]&&s.count(a[r]-a[l])&&a[r]!=a[r-1]&&a[l]!=a[l+1])

                {

                    f[l][r]=1;

                    for(int k=1;k<=32;k++) node[l][r].sum[k]=node[l+1][r-1].sum[k];

                    node[l][r].sum[id[a[r]-a[l]]]=1;

                }

                vector<int>put,cur_ans;

                if(!f[l][r])

                {

                    for(int k=l+1;k<=r-1;k++)

                    {

                        int cha1=a[r]-a[k],cha2=a[k]-a[l];

                        if(f[l][k-1]&&f[k][r]&&a[k]!=a[k-1])

                        {

                            f[l][r]=1;

                            put.clear();

                            for(int p=1;p<=32;p++)

                                if(node[l][k-1].sum[p]||node[k][r].sum[p])

                                    put.push_back(p);

                            if(cur_ans.size()==0)

                                for(int q=0;q<put.size();q++)

                                    cur_ans.push_back(put[q]);

                            if(cur_ans.size()!=0&&put.size()<cur_ans.size())

                            {

                                cur_ans.clear();

                                for(int q=0;q<put.size();q++)

                                    cur_ans.push_back(put[q]);

                            }

                        }

                        if(f[l+1][k-1]&&f[k+1][r-1]&&cha1==cha2&&s.count(cha1))

                        {

                            if(a[l]==a[l+1]||a[k-1]==a[k]||a[k]==a[k+1]||a[r-1]==a[r]) continue;

                            f[l][r]=1;

                            put.clear();

                            for(int p=1;p<=32;p++)

                                if(node[l+1][k-1].sum[p]||node[k+1][r-1].sum[p]||p==id[cha1])

                                    put.push_back(p);

                            if(cur_ans.size()==0)

                                for(int q=0;q<put.size();q++)

                                    cur_ans.push_back(put[q]);

                            if(cur_ans.size()!=0&&put.size()<cur_ans.size())

                            {

                                cur_ans.clear();

                                for(int q=0;q<put.size();q++)

                                    cur_ans.push_back(put[q]);

                            }

                        }

                    }

                }

                if(f[l][r])

                    for(int k=0;k<cur_ans.size();k++)

                        node[l][r].sum[cur_ans[k]]=1;

            }

        }

        for(int i=1;i<=n-1;i++)

            for(int j=i+1;j<=n;j++)

                if(f[i][j])

                    v.push_back((Edge){i,j,j-i+1});

        sort(v.begin(),v.end(),cmp);

        int cnt=0;

        for(int i=0;i<v.size();i++)

        {

            if(v[i].dis<minn) continue;

            //int k1=v[i].dis/minn;

            //if((maxx-minn)*k<v[i].dis-k*minn) continue;

            int k=v[i].dis/maxx+(v[i].dis%maxx==0?0:1);

            if((v[i].dis%maxx!=0)&&(v[i].dis%maxx+(k-1)*(maxx-minn)<minn)) continue;

            bool flag=true;

            for(int j=v[i].l;j<=v[i].r;j++)

                if(done[j]==1)

                    {flag=false;break;}

            if(flag==false) continue;

            for(int j=v[i].l;j<=v[i].r;j++)

                done[j]=1;

            for(int j=1;j<=32;j++)

                if(node[v[i].l][v[i].r].sum[j])

                    cnt++;

        }

        for(int i=1;i<=n;i++) if(done[i]) ans++;

        printf("Case #%d:\n%d %d\n",kkk,ans,cnt);

    }

    return 0;

}

最新文章

1. ORACLE中的LTRIM、RTRIM和TRIM
2. java enum
3. 【c#】对象转json字符串/字符串转Json对象
4. Android RecyclerView单击、长按事件标准实现：基于OnItemTouchListener + GestureDetector
5. SpringMVC注解@RequestParam全面解析
6. 分析一下FastDFS_java_client中TestClient.java这个文件以及跟它关联的这条线
7. [css][移动设备]禁止横竖屏时内容自动调整
8. Excel 宏
9. Oralce 处理字符串函数
10. php基础知识（二）---2017-04-14
11. 利用wamp配置虚拟主机
12. 数据保存策略（Retention Policies）
13. python取余
14. git 本地仓库与远程仓库建立连接
15. [No000011E]Python教程1/9-Python简介
16. 《大话设计模式》c++实现 状态模式
17. SmartGit（我工作中使用git图形化界面工具）
18. SpringBoot企业级博客开发
19. 6.26实力测试（小错笑cry）
20. WebViewJavascriptBridge测试示例

热门文章

1. 深入理解Javascript中构造函数和原型对象的区别（转存）
2. sqlserver,oracle,mysql等的driver驱动,url怎么写
3. loadView 和 viewDidLoad、viewDidunload 的区别
4. PHP笔试题及答案
5. kubenetes dns
6. centos7 安装docker-ce ，最新版本docker，docker阿里云加速
7. 高性能Web服务器Nginx的配置与部署研究（11）应用模块之Memcached模块的两大应用场景
8. Spring中Aspect的切入点的表达式定义细节
9. 在子页面使用layer弹出层时只显示遮罩层,不显示弹出框问题
10. iOS单选和全选