spoj EDIST dp string distance

http://www.spoj.com/problems/EDIST/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int f[2002][2002];
char a[2002], b[2002];
int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		memset(f, 127 / 3, sizeof(f));
		scanf("%s%s", a, b);
		int n = strlen(a), m = strlen(b);
		for (int i = 0; i < n; i++) f[i][0] = i;/////
		for (int i = 0; i < m; i++) f[0][i] = i;/////
		for (int i = 1; i <= n; i++)
		    for (int j = 1; j <= m; j++){
    			if (a[i-1] == b[j-1]) f[i][j] = f[i-1][j-1];
		        else f[i][j] = min(min(f[i-1][j], f[i][j-1]), f[i-1][j-1]) + 1;
    		}
        printf("%d\n", f[n][m]);
	}
	return 0;
}
时间: 2024-12-03 00:22:22

spoj EDIST dp string distance的相关文章

Json数据解析模拟美团界面显示_Android

<?xml version="." encoding="UTF-"?> <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android" android:layout_width="match_parent" android:layout_height="dp" android:background=&qu

Json数据解析模拟美团界面显示

<?xml version="." encoding="UTF-"?> <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android" android:layout_width="match_parent" android:layout_height="dp" android:background=&qu

网络编程Socket

 网络模型 OSI参考模型 TCP/IP参考模型 可以上网脑补 学的网络编程主要在应用层(我想android.JavaWeb.QQ.梦幻西游等吧,估计是).传输层和网际层混,每个层都有自己的协议规则. 传输层主要用TCP(同步:面向连接,数据量大).UDP(异步:面向无连接,大小限制在64k内,QQ聊天.网络视频用的UDP) 网际层主要用IP协议 应用层协议:HTTP 网络通讯要素 IP地址:标识网络上的电脑的,相当于给电脑取个唯一的名字   192.168.1.1,最大只能设置255这是字

网站设计资源:网站设计中最常用的表单插件

文章简介:网站项目中最常用的表单插件. 今天带来的是网站项目中最常用的表单插件. jQuery Complexify 网站有责任告诉用户他们设置的密码的质量,这款插件可以显示密码的复杂程度,通过视觉反馈把风险降到最低. 使用非常简单,示例 HTML 代码: 1 2 3 4 5 6 7 8 9 <script src="../assets/s/jquery.complexify.js"></script> <div id="demo"&g

java服务器应用

现在讨论一下服务器应用(程序)的问题,我把它叫作NameCollecor(名字收集器).假如多名用户同时尝试提交他们的E-mail地址,那么会发生什么情况呢?若NameCollector使用TCP/IP套接字,那么必须运用早先介绍的多线程机制来实现对多个客户的并发控制.但所有这些线程都试图把数据写到同一个文件里,其中保存了所有E-mail地址.这便要求我们设立一种锁定机制,保证多个线程不会同时访问那个文件.一个"信号机"可在这里帮助我们达到目的,但或许还有一种更简单的方式. 如果我们换

java数据报编程

大家迄今看到的例子使用的都是"传输控制协议"(TCP),亦称作"基于数据流的套接字".根据该协议的设计宗旨,它具有高度的可靠性,而且能保证数据顺利抵达目的地.换言之,它允许重传那些由于各种原因半路"走失"的数据.而且收到字节的顺序与它们发出来时是一样的.当然,这种控制与可靠性需要我们付出一些代价:TCP具有非常高的开销. 还有另一种协议,名为"用户数据报协议"(UDP),它并不刻意追求数据包会完全发送出去,也不能担保它们抵达的

Android模拟聊天工具

没有写界面,但是主要的代码都已经写出. import java.io.*; import java.net.*; class ChatDemo { public static void main(String [] args)throws Exception { DatagramSocket send1 = new DatagramSocket(); DatagramSocket rece1 = new DatagramSocket(10001); new Thread(new send(sen

java se-java udp发送端接收端变成问题求大神解答。

问题描述 java udp发送端接收端变成问题求大神解答. 采用了多线程,如果发送端输入的是英文,接收端可以正常接收. 但是如果发送端输入的是中文,接收端无法接收,而且程序会卡.这是怎么回事?代码如下: 主程序代码: public class ChatDemo { public static void main(String[] args) throws IOException { DatagramSocket dss=new DatagramSocket(); DatagramSocket d

Java中的网络编程

​ Java中的网路编程主要是Java的Socket编程,属于JavaEE中的高级的部分,以下内容是对java网路编程的一个小结,代码都是经过编译调试的   C/S程序应用:客户/服务器模式,如QQ客户端,客户端连到服务器上,一个C/S模式的应用必须有两套程序,一个是客户端的程序,一个是服务器程序. B/S程序应用:浏览器/服务器模式,如当下的各种网站都是B/S模式,所有的程序代码都在服务器上,用户通过浏览器去访问.   C/S程序分为两种:         基于TCP协议:Socket(套接字