本来以为是只很粗略的间距DP,后来发现直接区间DP是怪的,这玩意有后效性:刷完一整块从此立即同一片就换了。

思考

第一个功能应该是发在确立连接的时刻,如果房间里越2人口,则回前端一个误。
仲独我们得创造一个初的线程。
其三只凡是一个纯粹的前端开发工作,我们可激增两个图片,并每次标记上一致不好的职位,当下一个子的时节,画一个特别的子,并据此同样摆normal的分段覆盖上一个子。
季单凡是生在断开连接的当儿。

  设g[i]代表A串由1及i全部于刷成B的尽小步数,用f来更新g。

前言

前面我们已经形成了一个产生房间的五靠棋游戏,现在咱们将越来全面这个事物。这同一软我们打算新增的功力产生:

  • 前面我们加了房,但并没有限制房间只能进入2单人
  • 日增一个守护线程,统计时房的数据,后面我们将持续到这个守护线程的意义。
  • 亮及一个棋子落于哪儿
  • 去房间后会削减房间的人,并回收房间

  这样便管”空串变B串”解决了。但是咱是只要拿A串变B串,答案还需要统计一举。

实现

率先只效益。

    Room room = roomMap.get(roomId);
    if (room.enterRoom(session)){
        session.getUserProperties().put("roomId", roomId);
    }else{
        Result result = new Result();
        result.setSuccess(false);
        result.setErrMsg("进入房间失败");
        session.getBasicRemote().sendText(new Gson().toJson(result));
    }

万一以进入房间失败的时刻回来一个错误信息给前端即可。当然前端也使处理是错误信息咯。
次个作用,创建一个大概的Deamon,我们之所以一个context来传播运行时之片段参数。

    static {
        RunContext context = new RunContext(roomMap);
        DeamonThread deamonThread = new DeamonThread(context);
        Thread dThread = new Thread(deamonThread);
        System.out.println("Create Thread");
        dThread.start();
    }

俺们好当DeamonThread类中落实各种力量,例如每隔30s统计房间的总数。

    public void run() {
        while (true){
            try{
                System.out.println("RoomSize is[" + runContext.getRooms().size() + "]");
                Thread.sleep(30000);
            }catch (Exception e){

            }
        }
    }

其三只是一个前端功能,我们新增了个别张新的图片,用last_x,
last_y来表示达成一个棋子落于何处。一开始我们初始化为-1。

    if (x >= 0 && x < 15 && y >= 0 && y < 15) {
        if (chess == 1) {
            if (last_x > 0 && last_y > 0){
                context.drawImage(img_b, last_x * 40 + 20, last_y * 40 + 20);
            }
            context.drawImage(img_w_now, x * 40 + 20, y * 40 + 20);//绘制白棋
            chessData[x][y] = 1;
        }
        else {
            if (last_x > 0 && last_y > 0){
                context.drawImage(img_w, last_x * 40 + 20, last_y * 40 + 20);
            }
            context.drawImage(img_b_now, x * 40 + 20, y * 40 + 20);
            chessData[x][y] = 2;
        }
        judge(x, y, chess);
        last_x = x;
        last_y = y;
    }

季单,前面我们关系在onClose方法吃,有可卜的参数Session,我们可以通过之Session来取得到房间号。

    String roomId = (String)session.getUserProperties().get("roomId");
    Room room = roomMap.get(roomId);
    if (room != null){
        room.leaveRoom(session);
        if (room.getNowNumber() <= 0){
            roomMap.remove(roomId);
        }
    }
    System.out.println("Connection closed");

PO一摆图,现在的成为这样了。。。

图片 1

玩耍界面

  对于这种确定性只能用DP来开的、一般的易而生后效性的开,不妨状态而大气一点,直接忽略后效性带来的熏陶,再转移方式统计答案。

总结

咱而往前面挪了千篇一律步。这无异涂鸦重大都是有功力的周吧。后面我们针对片效果继续到。
源代码下载地址

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
#define FILE "4394"
using namespace std;

const int N = 110;
int n,f[N][N],g[N];
char A[N],B[N];

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void solve(){
  n=strlen(A+1);
  for(int i=1;i<=n;++i)f[i][i]=1;
  for(int len=1;len<n;++len)
    for(int i=1;i+len<=n;++i){
      int j=i+len;f[i][j]=f[i+1][j]+1;
      for(int k=i+1;k<=j;++k)
        if(B[i]==B[k])
          f[i][j]=min(f[i][j],f[i+1][k]+f[k+1][j]);
    }
  g[1]=A[1]==B[1]?0:1;
  for(int i=2;i<=n;++i){
    if(A[i]==B[i]){g[i]=g[i-1];continue;}
    g[i]=f[1][i];
    for(int j=1;j<i;++j)
      g[i]=min(g[i],g[j]+f[j+1][i]);
  }
  printf("%d\n",g[n]);
}

int main(){
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  while(~scanf("%s%s",A+1,B+1))solve();
  fclose(stdin);fclose(stdout);
  return 0;
}

  题目大意:有有限单字符串A,B,一次刷可将A串一段落刷成同一个字母,问至少要刷几浅才会拿A串变成B串。串长≤100。

 

  这个转移也是较有意思的,这里虽未做分析了。

  转移方程的合计是:如果以B串中,i和k是一样的,就可分开区间进行更新。

  for(int i=1;i<=n;++i)f[i][i]=1;
  for(int len=1;len<n;++len)
    for(int i=1;i+len<=n;++i){
      int j=i+len;f[i][j]=f[i+1][j]+1;
      for(int k=i+1;k<=j;++k)
        if(B[i]==B[k])
          f[i][j]=min(f[i][j],f[i+1][k]+f[k+1][j]);
    }

  证明:区间涂色有些许栽艺术:分成左右 /
先整个上一满又以中间上。

  结论:在涂色的时光,区间的一个端点,一定得看作第一独涂色。

  这个时段的转移方程就是:

图片 2图片 3

String painter

  g[1]=A[1]==B[1]?0:1;
  for(int i=2;i<=n;++i){
    if(A[i]==B[i]){g[i]=g[i-1];continue;}
    g[i]=f[1][i];
    for(int j=1;j<i;++j)
      g[i]=min(g[i],g[j]+f[j+1][i]);
  }

  同好据此面的支行问题想方式证明。

  这个时换方程就是这般:

  这个转移方程是杀抢眼的。

  首先赋值最酷情况,作为最特别价值,然后枚举k,进行创新。

  对于这种问题不如干脆利落一点,直接将
f[ ][ ]设成将空串(即未待考虑A与B的如出一辙)刷成B串的顶小次数。

  所以在换时,如果i和k是同的,则可起f[i][k]=f[i+1][k],只待以涂k的时光将任何区间涂上即足以了。

  分成左右是分问题,先周上的言语就是可优先选择这个端点涂。