首页 > 代码库 > [vijos1246]文科生的悲哀(二) 动态规划

[vijos1246]文科生的悲哀(二) 动态规划

背景

化学不及格的Matrix67无奈选择了文科。他必须硬着头皮艰难地进行着文科的学习。

描述

这学期的政治、历史和地理课本各有n章。每一科的教学必须按章节从前往后依次进行。若干章政治、若干章历史和若干章的地理内容可以合成一个教学阶段。年级计划将整个学期的内容分成若干个阶段进行教学。为了保证各科教学进度相同,年级规定每一个阶段包含的各科的章节数必须相同。一个阶段包含的章节越多,这个阶段所需要的课时也就越多。经过研究,假如某个阶段包含政史地各k章,则政治学习需要花费3^k天的课时,历史学习需要花费5^k天的课时,地理学习需要花费2^k天的课时,最后还需要4天的综合训练。一个阶段所花费的总时间是以上四项时间的和。

为了便于安排时间,学校希望每个阶段恰好需要若干周来完成。因此,划分出的每一个阶段所需要的天数都必须是7的整数倍(高三是没有星期六和星期天的)。

那么,这学期的课程最多可以划分成多少个阶段呢?你会想到,要想划分的阶段数最多,一个阶段完成一章的任务就行了(因为3^1+5^1+2^1+4=14是7的整数倍)。但问题没有这么简单。每个课本都可能有一些独立性较强的连续章节,它们具有很强的连续性,必须在一个阶段中完成。如果你已知所有不能划分在两个或两个以上的阶段中的连续章节,你还能计算出最多能安排多少个阶段吗?

格式

输入格式

第一行有两个用空格隔开的正整数n和m,分别表示各科课本的章节数和不可分割的连续章节的个数。

第二行到第m+1行,每行告诉了一个信息,该信息说明了哪一个课本的第几章到第几章必须一次性完成。同一科目给定的章节有可能重复或有重叠。

每一行信息分为两个部分。第一部分是“Politics:”、“History:”、“Geography:”三个字符串中的一个;第二部分是用“-”连接的两个数字x,y(1<=x<y<=n),表示该行第一部分所示的课本从第x章到第y章具有连续性。第二部分紧接在第一部分后面,没有任何符号分隔。

对于30%的数据,n,m<=10;
对于50%的数据,n,m<=1000;
对于100%的数据,n,m<=100 000。

输出格式

一个正整数,表示按照学校和年级的种种要求(见下)最多可以安排的阶段个数。

如果没有符合条件的安排方案,请输出-1。

注意:以下三个要求需要同时考虑。

1.每一个阶段包含的各科章数相同;
2.按时间函数计算出的各阶段所需天数必须是7的倍数;
3.给出的任一个连续章节都不能被分割开来。

样例1

样例输入1

8 3
Politics:1-2
History:5-6
Politics:1-4
Copy

样例输出1

3
Copy

限制

各个测试点1s

提示

样例说明:
最多可以安排三个阶段,具体方案如下:
第一阶段完成各科第1-6章的课程
第二阶段完成各科第7章的课程
第三阶段完成各科第8章的课程

Sample Input #2:
4 2
Geography:1-3
History:2-4

Sample Output #2:
-1

 

 

  这道题做了我一个上午………………orz

  一开始十分天真,注意到区间显然是可以合并之后(可以合并是因为一个阶段各科章节数一样)直接贪心了,能搞成一个阶段就搞成一个阶段……完美WA50

  事实上这个数据贪心就过不了:

18 3

Politics:3-6

Geography:7-12

History:13-18

  贪心结果是-1,正解是3。

  接着开始找题解但是却找不到,于是开始手糊正解。先是注意到,满足条件的章节数%6必然<3,且只有在区间交接处才有答案,其他地方都为-1;

  先合并区间并用pre[i]表示以i结尾的区间的起始位置。计算f[i]时只需用pre[i],pre[pre[i]],pre[pre[pre[i]]]……中满足条件的更新即可(因为f值并非递增所以不能在第一次更新后就退出)

  于是这样你就得到了在vijos上用时1700+s卡过的AC代码

  但这不行啊!显然是因为数据水评测机好才过的(xjoi上就T了……so sad……

  继续思考,最后发现假如i与某一个j=pre[pre[……pre[i]……]]的距离%6==0,那么显然在j之前对i满足条件的k必然对j也满足条件,所以f[j]就是j及之前的最大可更新值,所以更新后就可以直接跳出啦

  愉快的60+s AC~~~

评测结果及代码如下:

 

#状态耗时内存占用
#1  Accepted  3ms 4.332MiB
#2  Accepted  3ms 4.25MiB
#3  Accepted  2ms 4.25MiB
#4  Accepted  2ms 2.367MiB
#5  Accepted  2ms 2.25MiB
#6  Accepted  4ms 4.25MiB
#7  Accepted  9ms 3.195MiB
#8  Accepted  10ms 3.457MiB
#9  Accepted  14ms 3.625MiB
#10  Accepted  11ms 4.871MiB
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
char s[200000];
int n,m,T[200],a[200000],b[200000],c[200000],f[200000],pre[200000],ans,d[200000];
int tdigit(int l,int r){
    int x=0;
    for(int i=l;i<=r;i++)
    x=x*10+s[i]-0;
    return x;
}
void done(int x);
int main(){
    scanf("%d%d",&n,&m);
    T[P]=9;T[H]=8;T[G]=10;
    for(int i=1;i<=m;i++){
        scanf("%s",s);    int x=0,y=0;
        for(int i=T[s[0]];i<strlen(s);i++)if(s[i]==-){x=tdigit(T[s[0]],i-1);y=tdigit(i+1,strlen(s)-1);break;}
        a[x]++;d[y]++;
    }
    int p=0,num=1,w=1;
    for(int i=1;i<=n;i++){
        p+=a[i];p==0?c[i]=0:c[i]=num;p-=d[i];
        if(p==0)num++;
    }
    for(int i=1;i<=n;i++)if(c[i]==0||c[i]!=c[i+1])pre[i]=w,w=i+1;
    for(int i=1;i<=n;i++)if(c[i]!=0&&c[i]==c[i+1])f[i]=0;else done(i);
    printf("%d",f[n]?f[n]:-1);
}
void done(int x){
    int j=pre[x];
    while(j){
        if(f[j-1]&&(x-j+1)%6<3){
            f[x]=max(f[x],f[j-1]+1);
            if((x-j+1)%6==0)break;
        }
        j=pre[j-1];
    }
    if(j==0&&f[x]==0&&(x-j)%6<3)f[x]=1;
}

 

 

 

[vijos1246]文科生的悲哀(二) 动态规划