Kpop Music Party ZOJ – 3941(搜索/枚举)

题目链接

https://cn.vjudge.net/problem/ZOJ-3941

题目大意

Edward想去参加音乐会,每次参加完音乐会只之后都会持续K天的兴奋(从今天到今天+K-1天), 现在共有n场音乐会, 每场音乐会都有一个开始时间和结束时间,并且他能选择其中的M天去参加, 现在求他能兴奋的总天数最多。

解题思路

本来想贪心,优先把能连续选择的连续选完后把剩下的空按空间从大到小选择,但后来发现是不对的,因为在后来填空的时候有可能会覆盖到下一个已经选择的区间的一部分,这样就会造成浪费。
正确思路是从头开始,对于每个区间,仍然是优先把这段区间里的能连续选择的连续选择上,然后是否从当前区间最后一天在参加一次进行递归搜索,答案取搜索中的最大值。

AC代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k,cnt,res;
struct node
{
    ll x,y;
    bool operator < (const node &r)const
    {
        if(x==r.x)
            return y<r.y;
        return x<r.x;
    }
} a[22],b[22];
void dfs(ll pos,ll i,ll ans,ll num)
{
    if(num>k)
        return;
    if(num==k||i>=cnt+1)
    {
        res=max(res,ans);
        return;
    }
    ll len,p1,p2,p3,t;
    if(pos<b[i].y)//当前位置在当前区间右端点之前
    {
        //往后尽可能多的不重复的连续的选择
        len=min(b[i].y-pos,b[i].y-b[i].x+1);
        p1=len%m;
        if(p1==0)
            p2=len/m;
        else p2=len/m+1;
        if(p2+num>k)
        {
            res=max(res,ans+(k-num)*m);
        }
        p3=max(b[i].x+p2*m-1,pos+p2*m);
        t=p2*m;
        //选不选当前区间最后端点两种情况
        dfs(p3,i+1,ans+t,num+p2);
        dfs(b[i].y+m-1,i+1,ans+t+b[i].y+m-1-p3,num+p2+1);
    }
    else
    {
        //选不选当前区间右端点两种情况
        dfs(pos,i+1,ans,num);
        dfs(b[i].y+m-1,i+1,ans+b[i].y+m-1-pos,num+1);
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int i,j;
        cnt=0;
        cin>>n>>m>>k;
        for(int i=1; i<=n; i++)
        {
            cin>>a[i].x>>a[i].y;
        }
        sort(a+1,a+1+n);
        for(ll i=1; i<=n; i++)//合并区间
        {
            ll maxx=a[i].y;
            ll lll=a[i].x;
            while(i<=n&&a[i].x<=maxx)
            {
                maxx=max(maxx,a[i].y);
                i++;
            }
            b[++cnt]=node{lll,maxx};
            if(i>n)
                break;
            i--;
        }
        res=0;
        //搜索所有情况,结果取max
        dfs(0,1,0,0);
        cout<<res<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注