脑子一抽用0初始化DP。。。TLE到爆了。。。。
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 1203 | Accepted: 319 | Special Judge | ||
Description
Three turtles are crawling along a road. One turtle says: "There are two turtles ahead of me."
The other turtle says: "There are two turtles behind me." The third turtle says: "There are
two turtles ahead of me and two turtles behind me." How could this have happened?
The answer is -- the third turtle is lying!
Input
Output
Sample Input
5 0 2 0 3 2 1 1 2 4 0
Sample Output
2 1 4
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1100;
int n,cnt[maxn][maxn],dp[maxn],s[maxn][3],pre[maxn],ans[maxn][2];
void init()
{
memset(cnt,0,sizeof(cnt));
memset(dp,-1,sizeof(dp));
}
int DP(int x)
{
if(dp[x]!=-1) return dp[x];
if(x==0) return dp[x]=0;
int ret=0;
for(int i=1;i<=x;i++)
{
if(ret<=DP(x-i)+min(cnt[x-i][n-x],i))
{
ret=dp[x-i]+min(cnt[x-i][n-x],i);
pre[x]=x-i;
ans[x][0]=x-i;ans[x][1]=n-x;
}
}
return dp[x]=ret;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=0;i<n;i++)
{
scanf("%d%d",&s[i][0],&s[i][1]);
cnt[s[i][0]][s[i][1]]++;
}
int res=DP(n);
for(int i=n;i;i=pre[i])
{
for(int j=0,k=i-pre[i];k&&j<n;j++)
{
if(s[j][0]==ans[i][0]&&s[j][1]==ans[i][1])
{
k--;
s[j][2]=1;
}
}
}
printf("%d",n-res);
for(int i=0;i<n;i++) if(!s[i][2]) printf(" %d",i+1);
putchar(10);
}
return 0;
}
POJ 2168 Joke with Turtles,布布扣,bubuko.com
原文：http://blog.csdn.net/ck_boss/article/details/22933019