uva 111 - History Grading (dp, LCS)

时间:2022-09-01 22:25:46

题目链接

题意:给N,第二行是答案,n个数c1---cn, 代表第一个的顺序是c1,第二个数顺序是c2;

下面每一行是学生的答案,格式同上。

注意:这个给的顺序需要处理一下,不能直接用。

思路:LCS。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define Max(a,b)((a)>(b)?(a):(b))
const int maxn= + ;
int a[maxn], b[maxn], n, d[maxn][maxn]; void LCS()
{
memset(d, , sizeof(d));
int i, j;
for(i = ; i <= n; i++)
for(j = ; j <= n; j++)
if(a[i]==b[j])
d[i][j] = d[i-][j-] + ;
else
d[i][j] = Max(d[i-][j], d[i][j-]);
cout<<d[n][n]<<endl;
}
int main()
{
int i, x;
cin>>n;
for(i = ; i <= n; i++)
{
cin>>x;
a[x] = i;
}
while(cin>>x)
{
b[x] = ;
for(i = ; i <= n; i++)
{
cin>>x;
b[x] = i;
}
LCS();
}
return ;
}

uva 111 - History Grading (dp, LCS)的更多相关文章

  1. uva 111 History Grading(lcs)

    题目描述 在信息科学中有一些是关于在某些条件限制下,找出一些计算的最大值. 以历史考试来说好了,学生被要求对一些历史事件根据其发生的年代顺序来排列.所有事件顺序都正确的学生无疑的可以得满分.但是那些没 ...

  2. uva 111 History Grading&lpar;最长公共子序列)

    题目连接:111 - History Grading 题目大意:给出一个n 代表序列中元素的个数, 然后是一个答案, 接下来是若干个同学的答案(直到文件结束为止), 求出两个序列的最长公共子序列, 注 ...

  3. UVa 111 - History Grading &lpar;by 最长公共子序列 &rpar;

     History Grading  Background Many problems in Computer Science involve maximizing some measure accor ...

  4. UVa 111 History Grading (简单DP,LIS或LCS)

    题意:题意就是坑,看不大懂么,结果就做不对,如果看懂了就so easy了,给定n个事件,注意的是, 它给的是第i个事件发生在第多少位,并不是像我们想的,第i位是哪个事件,举个例子吧,4 2 3 1, ...

  5. UVA 111 History Grading

    读题读了好久,其实就是在输入数据时要对数据的位置进行相应的改变 #include<iostream> #include<cstring> #include<cstdio& ...

  6. UVA 11404 Palindromic Subsequence&lbrack;DP LCS 打印&rsqb;

    UVA - 11404 Palindromic Subsequence 题意:一个字符串,删去0个或多个字符,输出字典序最小且最长的回文字符串 不要求路径区间DP都可以做 然而要字典序最小 倒过来求L ...

  7. UVA&period;10192 Vacation &lpar;DP LCS&rpar;

    UVA.10192 Vacation (DP LCS) 题意分析 某人要指定旅游路线,父母分别给出了一系列城市的旅游顺序,求满足父母建议的最大的城市数量是多少. 对于父母的建议分别作为2个子串,对其做 ...

  8. UVA&period;10066 The Twin Towers &lpar;DP LCS&rpar;

    UVA.10066 The Twin Towers (DP LCS) 题意分析 有2座塔,分别由不同长度的石块组成.现在要求移走一些石块,使得这2座塔的高度相同,求高度最大是多少. 问题的实质可以转化 ...

  9. UVA 111(LCS问题)

     History Grading  Background Many problems in Computer Science involve maximizing some measure accor ...

随机推荐

  1. 谷歌浏览器下载地址 chrome最新版本 百度云地址

    每次下载更新谷歌浏览器是一件很蛋疼的事情.百度搜索"谷歌浏览器下载地址",居然有很多骗子网站,相信有很多不知所以的人中招了.收集了一些chrome的安装包,放在了百度云里面(打不开 ...

  2. 2014Ember带来怎样的变化?

    每隔几个月的时间,Ember的核心团队就会聚在一起讨论目前遇到的各种问题,并决定下一季度需要优先处理的各种事务. 这一次,在俄勒冈州的波特兰,大家聚在一起,商讨2014年的发展方向. 开发工具 &am ...

  3. Bootstrap 进度条媒体对象和 Well 组件

    一.Well 组件 这个组件可以实现简单的嵌入效果. //嵌入效果 <div class="well"> Bootstrap </div> //有 lg 和 ...

  4. BOX2D测试

    ; ; Box2DTestLayer = cc.Layer.extend({ world:null, //GLESDebugDraw *m_debugDraw; ctor:function () { ...

  5. NetworkOnMainThreadException

    来自:http://www.2cto.com/kf/201402/281526.html NetworkOnMainThreadException extends RuntimeException j ...

  6. Properties类读写&period;properties配置文件

    package com.hzk.utils; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFo ...

  7. 用bat启动sqlserver服务

    声明下这个脚本不是我写的,忘了是从哪看到的了,在此分享给大家,因为在我的理解中技术就是用来分享的,,希望原创作者看到了不要介意. 1.创建个文本,将后缀名改成.bat 2.将下边语句粘贴进去,然后保存 ...

  8. 遇到报ClassNotFoundException&colon; Didn&&num;39&semi;t find class &quot&semi;&period;&period;&period;Activity&quot&semi; on path&colon; DexPathList

    有一个工程,本来运行是正常的,我想把它移植到另一台PC上,结果报: java.lang.RuntimeException: Unable to instantiate activity Compone ...

  9. git push 报错 &quot&semi;Peer certificate cannot be authenticated with known CA certificates&quot&semi;

    使用git push -u origin master 命令向远程仓库提交代码时报错:Peer certificate cannot be authenticated with known CA ce ...

  10. g&plus;&plus; 学习笔记

    gcc and g++分别是GNU的c & c++编译器.gcc/g++在执行编译的时候一般有下面4步: 1 预处理,生成.i的文件. 命令如下:g++ -E  test.cpp 此命令只进行 ...