由于這題目要求輸出的時候序号要盡量小，沒看到，是以呵呵了。
屬于dp，注釋都在代碼中間了。貌似自己面對這種要輸出答案解，并且要求序号小的題目很是蛋疼。
//Codeforces Round #338 (Div. 2) C. Running Track (dp)
#include<stdio.h>
#include<cstdlib>
#include<istream>
#include<algorithm>
#include<vector>
#include<string.h>
#define mod 105225319
#define maxn 100000
using namespace std;
int dp1[2105][2105],dp2[2105][2105],dp[2105];
int main()
{
//freopen("d:\\in.txt","r",stdin);
char s1[2500],s2[2500],_s1[2500];
scanf("%s %s",s1,s2);
int len1=strlen(s1),len2=strlen(s2),i;
for(i=0;i<len1;i++)
_s1[len1-i-1]=s1[i];
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
memset(dp,0x3f3f3f3f,sizeof(dp));
int j,k,cnt1[2500],cnt2[2500];
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
{
if(s1[i-1]==s2[j-1])
{
if(dp1[i][j]<dp1[i-1][j-1]+1)
{
dp1[i][j]=dp1[i-1][j-1]+1;
if(dp1[cnt1[j]][j]<dp1[i][j]) //這裡要注意判斷序号要小
cnt1[j]=i;
}
}
if(_s1[i-1]==s2[j-1])
{
if(dp2[i][j]<dp2[i-1][j-1]+1)
{
dp2[i][j]=dp2[i-1][j-1]+1;
if(dp2[cnt2[j]][j]<=dp2[i][j]) //這裡判斷條件有一點不同
cnt2[j]=i;
}
}
}
dp[0]=0;
for(i=1;i<=len2;i++)
for(j=1;j<=len1;j++)
{
dp[i]=min(dp[i],dp[i-dp1[j][i]]+1);
dp[i]=min(dp[i],dp[i-dp2[j][i]]+1);
//printf("dp[%d]=%d\n",i,dp[i]);
}
int ans1[2500],ans2[2500],cnt=dp[len2];
if(cnt>2105)
printf("-1\n");
else
{
for(i=len2;i>=1;i--)
for(j=i;j>=0;j--)
{
if(dp[i]==dp[i-j]+1&&dp1[cnt1[i]][i]==j)
{
ans1[cnt]=cnt1[i]-j+1;
ans2[cnt]=cnt1[i];
i=i-j+1;
cnt--;
break;
}
if(dp[i]==dp[i-j]+1&&dp2[cnt2[i]][i]==j)
{
ans1[cnt]=len1-cnt2[i]+j;
ans2[cnt]=len1-cnt2[i]+1;
i=i-j+1;
cnt--;
break;
}
}
printf("%d\n",dp[len2]);
for(i=1;i<=dp[len2];i++)
printf("%d %d\n",ans1[i],ans2[i]);
}
return 0;
很好啊