首页 > 其他 > 详细

la4394

时间:2018-09-23 00:44:49      阅读:710      评论:0      收藏:0      [点我收藏+]

题解:

首先区间dp是比较好想到的

然后我感觉接下来就是乱搞。。。

我们会发现接下来的操作 无非就是 用一种颜色去覆盖这整个区间 然后在做

于是我用了比较暴力的做法,f[i][j][k]表示i-j这段区间被k颜色完全覆盖

那么转移就是枚举f[i][kk][k] f[kk+1][j][k]

另外要注意还有同层之间可以用全部覆盖成一个颜色来转移

最后再跑一遍dp(这时候已知了g[i][j] (覆盖i-j的最小值))

代码:

#include <bits/stdc++.h>
using namespace std;
#define rint register int 
#define IL inline
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
char s1[200],s2[200];
int f[200][200][27],g[200][200],p[200];
const int INF=1e9;
int main()
{
  freopen("1.in","r",stdin);
  freopen("1.out","w",stdout);
  ios::sync_with_stdio(false);
  while( cin>>s1>>s2)
  {
  int n=strlen(s1);
  dep(i,n,1) s1[i]=s1[i-1],s2[i]=s2[i-1];
  rep(i,1,n)
    rep(j,i+1,n) g[i][j]=INF;
  rep(i,1,n)
  {
    rep(k,0,25) f[i][i][k]=2;
    f[i][i][s2[i]-a]=1;
    if (s1[i]==s2[i]) g[i][i]=0; else g[i][i]=1;
  }
  rep(i,2,n)
    rep(j,1,n-i+1)
    {
      int h=j,t=j+i-1;
      rep(k,0,25)
      {
        f[h][t][k]=INF;
        rep(k1,h,t-1)
        {
          f[h][t][k]=min(f[h][t][k],f[h][k1][k]+f[k1+1][t][k]-1);
        }
        g[h][t]=min(g[h][t],f[h][t][k]);
      }
      rep(k,0,25) f[h][t][k]=min(f[h][t][k],g[h][t]+1); 
    } 
  rep(i,1,n)
  {
    p[i]=INF;
    rep(j,0,i-1)
      p[i]=min(p[i],p[j]+g[j+1][i]);
  }
  cout<<p[n]<<endl;
  }
  return 0;
}

 

la4394

原文:https://www.cnblogs.com/yinwuxiao/p/9691673.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!