发布于 由itewqq

[DP][思维] ZOJ3161 Damn Couples

题目最重要的是理解题意。。然后第二重要的是把原来的分散的点变成连续的：因为如果一开始的时候list上两个人就不相邻这时候最好就直接宣布了这个8g，因为这时候他们不会有任何一个人离开，这些操作之后也不用考虑了，这一步操作肯定的是最优的。

然后剩下的就是一块一块的被8g连起来的段，他们两两有一个8g，然后这时候可以用类似于矩阵链乘的算法，枚举第一次宣布的8g点，然后分成左右两块计算。max表示枚举断点取最大值，min表示顾客的想法：他们要让答案尽量小。

//#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=16000+5;
const int mod=1e9+7;

int F[505]={0,1,1,1};//F[3]?
int dp(int k)
{
    if(F[k]!=0)
        return F[k];
    for (int i=1;i lst[225005];

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    dp(503);
    int n,m,cnt=0,a,b;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;
        for (int i=0;ib)swap(a,b);
            if(b-a!=1)
                continue;

            lst[cnt].first=a,lst[cnt++].second=b;
        }
        sort(lst,lst+cnt);
        lst[cnt].first=-2,lst[cnt].second=-3;
        int f=0,ans=n;
        for (int i=0;i

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。