大致题意:
一个书架共有n层,每层m本书,现在要使得每一层的书都按照字典序不降的排列,每次可以把一本书移动到这本书所在层的另一个位置,求完成所有n层所需要的最少移动次数。
大致思路:
对于每层,移动次数等于m-lis。统计每一层的再相加即可。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
string name[100];
int dp[100];
int lis()
{
int i,j,res=0;
for(i=0;i<100;i++)dp[i]=1;
for(i=0;i<m;i++){
for(j=0;j<i;j++){
if(name[j]<=name[i]){
if(dp[j]+1>dp[i]){
dp[i]++;
}
}
}
res=max(dp[i],res);
}
return res;
}
int main()
{
int ans,i,j,a,b,c;
while(cin>>n>>m)
{
ans=0;
getchar();
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
getline(cin,name[j]);
}
ans+=(m-lis());
}
cout<<ans<<endl;
}
return 0;
}
分享到:
相关推荐
ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...
ZOJ 1002的具体内容未知,但常见的ACM题目类型包括但不限于:排序与查找、图论、动态规划、贪心算法、数学问题、字符串处理等。因此,这个C++程序可能涉及以上某一种或多种算法的组合。 C++语言在编程竞赛中广泛...
3. **字符串处理**:ZOJ题目中往往包含许多字符串处理问题,如模式匹配、字符串比较、最长公共子序列等。源代码会展示如何高效地操作字符串。 4. **数学知识**:部分题目可能需要运用到高等数学知识,如组合数学、...
在算法竞赛中,字符串处理是一个常见的主题,可能涉及到的操作包括但不限于编辑距离(Levenshtein Distance)、最长公共子序列(Longest Common Subsequence)或者其他的字符串匹配算法。"求串相似度"通常是指计算两...
【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...
4. **动态规划**:背包问题、最长公共子序列、最短路径、最长上升子序列等,动态规划能有效地解决具有重叠子问题和最优子结构的复杂问题。 5. **图论**:最小生成树(Prim 或 Kruskal 算法)、最短路径(Floyd-...
3. **动态规划(DP)**:动态规划是一种强大的问题解决方法,适用于解决最优决策问题,如背包问题、最长公共子序列、矩阵链乘法等。解题报告中的DP思路通常包括状态定义、状态转移方程和边界条件。 4. **贪心算法**...
例如,动态规划在解决背包问题、最长公共子序列、最小编辑距离等问题上有着广泛的应用;图论则涉及到最短路径算法(Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法)等。 此外,源码中...
DP在解决复杂问题时有着广泛的应用,例如背包问题、最长公共子序列、最短路径等。代码集可能会包含各种类型的DP模板和实例解析。 3. **贪心算法**:贪心策略通常用于求解局部最优解的问题,如活动选择问题、霍夫曼...
在编程竞赛和算法设计中,动态规划经常被用来解决如背包问题、最长公共子序列、最短路径等经典问题。动态规划的核心思想是记忆化,避免重复计算,以提高效率。 在学习和使用这个压缩包时,初学者可以从以下几个方面...
zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...
《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...
Problem Arrangement zoj 3777
浙江大学ZOJ(Zhejiang University Online Judge)是一个在线编程练习平台,主要服务于计算机科学和技术的学习者,特别是对算法和编程有浓厚兴趣的学生。这个平台提供了大量的编程题目,涵盖了各种难度和主题,帮助...
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...
3. **字符串处理**:ZOJ中的许多题目涉及到字符串操作,如模式匹配、字符串比较、最长公共子序列等。掌握字符串处理技巧对解题至关重要。 4. **数学应用**:部分题目需要运用到离散数学、组合数学、数论等领域的...
标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...
【ZOJ1003 Crashing Balloon】这个问题是一个经典的计算机科学竞赛编程题目,主要涉及动态规划(Dynamic Programming, DP)和贪心算法(Greedy Algorithm)的知识点。在这个问题中,参赛者需要编写程序来模拟气球...