还是整理题目吧
Prince and Princess
题意：求最长公共子序列。
思路：要用n*log(n)的写法，就是之前说过的，将第一个序列每个数的位置保存位置，当第二个序列也出现这个数时保存进一个新数列，最后对新数列求最长上升子序列。
const int maxn=252;
int dp[maxn*maxn];
int a[maxn*maxn];
int Lis(int n)
{
int len=1,i,low,high,mid;
dp[1]=1;
for(i=2;i<=n;i++)
{
low=1;
high=len;
while(low<=high)
{
mid=(low+high)/2;
if(a[i]>dp[mid]) low=mid+1;
else high=mid-1;
}
dp[low]=a[i];
if(low>len) len=low;
}
return len;
}
map<int,int>mp;
int main()
{
int T;
int Case=0;
scanf("%d",&T);
while(T--)
{
int x,n,p,q;
mp.clear();
scanf("%d%d%d",&n,&p,&q);
for(int i=1;i<=p+1;i++)
{
scanf("%d",&x);
mp[x]=i;
}
int cnt=0;
for(int i=1;i<=q+1;i++)
{
scanf("%d",&x);
if(mp[x])
{
a[++cnt]=mp[x];
}
}
printf("Case %d: %d\n",++Case,Lis(cnt));
}
}
Happy Birthday
题意：有n个盘子，依次选过去，你可以选或者不选，也可以放在堆的上面或者下面，但是必须满足上面的盘子是小于等于下面的盘子的，求最长是多少
思路：先求出每一个位置的最长上升，与最大下降。然后就可以想如果我们从第i个开始拿的话，那么我们可以在遇到它之后大于它的盘子j，那么我们需要找的就是以较大为起点的Lis，再加上小的Lds；遇到小的话，情况相反。
int a[1005];
int dp1[1005];
int dp2[1005];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>=1;i--)
{
dp1[i]=dp2[i]=1;
for(int j=n;j>i;j--)
{
if(a[i]>=a[j]) dp1[i]=max(dp1[i],dp1[j]+1);
if(a[i]<=a[j]) dp2[i]=max(dp2[i],dp2[j]+1);
}
}
int ans=-1;
for(int i=1;i<=n;i++)
{
ans=max(ans,max(dp1[i],dp2[i]));
for(int j=i+1;j<=n;j++)
{
if(a[i]<a[j]) ans=max(ans,dp1[i]+dp2[j]);
else if(a[i]>a[j]) ans=max(ans,dp1[j]+dp2[i]);
}
}
cout<<ans<<endl;
}
}
hdu 2476 String painter
题意：给出两个字符串a,b，依次可以改变a的一个连续区间变为同一个字母，问最少次操作将a变为b。
这是一个比较经典的区间dp。
思路：首先处理出来空白区间刷成b的最小步数作需处理。然后
if(s1[i]==s2[i]) ans[i]=ans[i-1];//如果相同，那么上一为刷的时候顺便就可以出完这一位
else
{
for(int j=0;j<i;j++)
{
ans[i]=min(ans[i],ans[j]+dp[j+1][i]);//找前面的分段点分别刷
}
}
还是看代码吧
char s1[105],s2[105];
int ans[105];
int dp[105][105];
int main()
{
while(scanf("%s%s",s1,s2)!=EOF)
{
int len=strlen(s1);
memset(dp,0,sizeof(dp));
memset(ans,0,sizeof(ans));
for(int i=0;i<len;i++){for(int j=i;j<len;j++) dp[i][j]=j-i+1;}
for(int j=0;j<len;j++)//处理将白板刷成b的最小步数
{
for(int i=j;i>=0;i--)
{
dp[i][j]=dp[i+1][j]+1;
for(int k=i+1;k<=j;k++)
{
if(s2[i]==s2[k]) dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]); //如果前面有相同的，就可以减少一次一下顺便把后面的刷好
}
}
}
for(int i=0;i<len;i++) ans[i]=dp[0][i];
for(int i=0;i<len;i++)
{
if(s1[i]==s2[i]) ans[i]=ans[i-1];
else
{
for(int j=0;j<i;j++)
{
ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
}
}
}
cout<<ans[len-1]<<endl;
}
}
Taekwondo
题意：给出两组数，求数量少的一组全部和另一组匹配求abs(a[i]-b[j])的加和最小值。
思路：就是dp[i][j]表示a数列前i个数和b数列前j个数匹配的最小值，状态转移就取决与找max(a的第i位上的数是否与匹配)
const int N=505;
double a[N],b[N],c[N];
double dp[N][N];
int n,m;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%lf",&a[i]);
for(int i=0;i<m;i++) scanf("%lf",&b[i]);
if(n>m)
{
for(int i=0;i<n;i++) c[i]=a[i];
for(int i=0;i<m;i++) a[i]=b[i];
for(int i=0;i<n;i++) b[i]=c[i];
swap(n,m);
}
sort(a,a+n);
sort(b,b+m);
dp[0][0]=fabs(a[0]-b[0]);
for(int i=1;i<m;i++) dp[0][i]=min(fabs(a[0]-b[i]),dp[0][i-1]);
for(int i=1;i<n;i++)
{
dp[i][i]=dp[i-1][i-1]+fabs(a[i]-b[i]);
for(int j=i+1;j<m;j++)
{
dp[i][j]=min(dp[i-1][j-1]+fabs(a[i]-b[j]),dp[i][j-1]);
}
}
printf("%.1lf\n",dp[n-1][m-1]);
}
}