问题分析

我们需要找到一组乌龟的坐标分配，使得尽可能多的乌龟说真话（即其陈述的前后乌龟数量与实际相符），从而最小化必须说谎的乌龟数量。关键在于： 说真话的乌龟的陈述 ($a_i$, $b_i$) 必须满足：存在一个坐标分配，使得恰好有 $a_i$ 只乌龟在其前方（坐标严格更大），$b_i$ 只乌龟在后方（坐标严格更小）。 同一坐标的乌龟视为一组，组内乌龟看不到同组的其他乌龟，因此组内乌龟的 $a_i$ 和 $b_i$ 必须相同（因为它们的前后乌龟数量相同）。

解题思路

分组：将乌龟按 $(a, b)$ 分组，每组内的乌龟陈述相同。

构造有效序列：对于每个可能的起始组（$a=0$，因为最前方的乌龟前方无乌龟），按以下规则构造序列： 下一组的 $a$ 必须等于当前所有组的总大小（因为前方乌龟数等于前面所有组的乌龟总数）。 下一组的 $b$ 必须严格小于前一组的 $b$（因为位置越靠后，后方乌龟数越少）。 每组的大小不能超过 $n - a - b$（因为当前组的乌龟数最多为 $n - a - b$，否则无法满足前后乌龟数）。

贪心选择：在每一步选择 $b$ 最大的可能组（确保后续有更多分组可能），以最大化真话乌龟数量。

代码

#include <cstring>
#include <vector>
#include <utility>
using namespace std;
#define N 1010

int n;
int w[N][N];
int dp[N] , p[N];
struct tur
{
   int a,b,c;
}t[N];

void solve()
{
   memset(dp,0,sizeof(dp));
   memset(p,-1,sizeof(p));

   for(int i = 1; i <= n; i++)
      for(int j = 0; j<n; j++)
         if(dp[j] + w[j+1][i] > dp[i])
         {
            dp[i] = dp[j] + w[j+1][i];
            p[i] = j;
         }

   bool used[N];
   memset(used,false,sizeof(used));
   int pre,now,count,c;
   now = n;
   count = 0;
   while(1) //沿路径返回并标记说了真话的乌龟
   {
      pre = p[now];
      if(pre == -1) break;
      //区间为[pre+1,now]
      c = w[pre+1][now]; //有多少只重叠的乌龟
      for(int i=0; i<n && c; i++)
         if(t[i].a == pre && t[i].b == n-now)
         {
            used[i] = true;
            c--;
            count++;
         }
      now = pre;
   }
   printf("%d",n-count);
   for(int i=0; i<n; i++)
      if(!used[i])
         printf(" %d",i+1);
   printf("\n");
}

int main()
{
   while(scanf("%d",&n)!=EOF)
   {
      memset(w,0,sizeof(w));
      for(int i=0; i<n; i++)
      {
         int a,b;
         scanf("%d%d",&a,&b);
         t[i].a = a; t[i].b = b;
         t[i].c = n - t[i].a - t[i].b;
         w[a+1][n-b]++;
         if(w[a+1][n-b] > t[i].c)
            w[a+1][n-b] = t[i].c;
      }
      solve();
   }
   return 0;
}