在 SPOJ 上解决 JUICE 时，这个解决方案有什么问题？

Question

问题是：

Jerry 迷失在有趣的游戏中：水果忍者。 Fruit Ninja 是一款 iPhone 和 iPad 的游戏，玩家切下屏幕底部的水果，一次切下两个以上的水果即可获得奖励。水果一旦切开，就会碎成小块，不能再切了。

经过几个月的训练，他成为了这个游戏的高手。实际上，他可以随时切掉屏幕上所有的水果。杰瑞还有一个坏习惯，就是不愿意留下一些水果留着以后砍。也就是说，杰瑞切完水果后，屏幕上所有的水果都碎了，一个也没有。这就是为什么他所有的朋友都称他为榨汁机。

现在他只考虑奖金，当他切两个以上的水果时，他可以获得与当时切水果数量相同的一些奖金分数。例如，杰瑞一片切4个水果，他这一片可以得4分。

杰瑞拿到水果时间表后，就知道了每一个水果的出现时间和消失时间。他只能在出现时间和消失时间之间将水果切成碎片。他想知道他能获得的最大可能奖励分数。

输入

有几个测试用例；输入的第一行包含一个整数 T，表示测试用例的数量。 (T <= 200)

对于每个测试用例，第一行包含一个整数N，表示水果的总数。 (1 <= N <= 1000)

接下来N行，每行描述一个水果。对于每一行，有两个整数 Xi 和 Yi，其中 Xi 是水果出现的时间，Yi 是这个水果消失的时间。 (0 <= Xi <= Yi <= 1000000000)

输出

对于每个测试用例，输出一个整数表示 Jerry 可能获得的最高分数。有关详细信息，请参阅示例。

例子

输入： 1个 10 1 10 2 11 3 12 4 13 13 14 14 15 13 19 20 22 21 23 22 24

输出：案例 #1：10

代码如下：它以start time.dp[i] 占第i 个水果出现的时间为基础对时间间隔进行排序。我们只会在出现水果时进行切割，因为它会涵盖所有情况

#include<iostream>
#include<vector>
#include<algorithm>
#include<memory.h>
using namespace std;
struct node
{
    int x,y;
};
int cmp(node a,node b)
{
    if(a.x!=b.x)
    return a.x<b.x;
    return a.y<b.y;
}
int main()
{
    int test;
    cin>>test;
    int t=0;
    int dp[1002];
    while(test--)
    {
        t++;
        int n;
        cin>>n;
        vector<node> v(n);
        for(int i=0;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            v[i].x=a;
            v[i].y=b;
        }
        sort(v.begin(),v.end(),cmp);
        memset(dp,0,sizeof(dp));
        int mx=0;
        for(int i=0;i<n;i++)
        {
            int id=100000,match=0;
            for(int j=0;j<=i;j++)
            {
                if(v[j].y>=v[i].x)
                {
                    id=min(id,j);
                    match++;
                }
            }
            for(int j=id;j<=i;j++)
            {
                if(match>2)
                dp[i+1]=max(dp[i+1],dp[j]+match);
                else
                dp[i+1]=max(dp[i+1],dp[j]);
                if(v[j].y>=v[i].x)
                match--;
            }

            dp[i+1]=max(dp[i+1],dp[i]);
            mx=max(mx,dp[i+1]);

        }
        cout<<"Case #"<<t<<": "<<mx<<"\n";
    }
    return 0;
}

Answer 1

当有一些段开始时间相同时，可能是错误的。

我用你的代码运行这个测试用例：

10

1 1

1 2

3 3

1 4

3 5

3 6

3 7

8 8

3 9

3 10

你的代码输出 10 但答案实际上是 9

因为这个测试用例，我也有几个 WA，在我处理完这个案例后得到了 AC...我将分享我的经验，请看看它是否与您相同。

使用这个测试用例，我的代码会输出10，我将快速解释如下：

令 dp(i) 为您在第 i 个片段的开始时间进行最后一次切割的状态

显然，对于所有 j < i

，dp(i) = 最大值（dp(j) + 段数（在 j 之后）与第 i 个段相交）

物理上，这意味着 你在第 j 个片段的开始时间 有倒数第二个剪辑这是合乎逻辑的 except if 第j和第i段的开始时间是一样的！那不是2个不同的cut而是同一个cut！

要解决这个问题，正确的方法是只选择具有相同开始时间的连续段的最后一段！

(假设段已经按开始时间排序，下面的顺序就是排序后的顺序)

这是错误，我的程序（可能也是你的）给出了输出 10，因为（使用基于 0 的）

DP(9) = DP(6) + # [7,9]

中的重叠段

= 7 + 3 = 10！

再深入一点，DP(6) = 7其实是对的，因为它没有考虑后面的段。但是 你不应该使用 DP(6) 来更新 X>6 的任何 DP(X)！ 因为 最后一个段具有相同的开始时间（第 6 个段)是第8段

简而言之，如果我们使用一些不是最后一个与自身具有相同开始时间的DP状态来更新其他DP状态，可能会出错。

我的解决方案是，当我在第 i 个段上进行 DP 时，每当我发现某些段 j 与段 i (j < i) 具有相同的开始时间时，我设置 DP(j)到负无穷大，这样它就不能优化到足以更新其他状态。

已编辑：添加了接受的代码 根据OP的要求，以下是我接受的代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define INF 1LL<<28
using namespace std;

int T,n;
int dp[1005];
pii a[1005];
int main(){
 scanf("%d", &T);
 for(int qwe=1; qwe <= T; qwe++){
  scanf("%d", &n);
  for(int i=0; i<n;i++) scanf("%d%d", &a[i].x, &a[i].y);
  sort(a, a+n);
  memset(dp,0,sizeof(dp));
  
  for(int i=0; i<n;i++){
   int cnt = 0;
   for(int j=i-1; j>=0; j--){
    if(a[j].x == a[i].x){dp[j] = -INF; cnt++; continue;}
    cnt += (a[i].x >= a[j+1].x && a[i].x <= a[j+1].y);
    dp[i] = max(dp[i], dp[j] + (cnt>2? cnt:0));
   }
   
   cnt += (a[i].x >= a[0].x && a[i].x <= a[0].y);
   dp[i] = max(dp[i], (cnt>2? cnt:0));
  }
  printf("Case #%d: %d\n", qwe, dp[n-1]);
 }
 return 0; 
}

在 SPOJ 上解决 JUICE 时，这个解决方案有什么问题？

What is wrong with this solution while solving JUICE on SPOJ?

c++

algorithm

dynamic-programming