`
暴风雪
  • 浏览: 389000 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[最长不降子序列]zoj 3523:Bookcase

阅读更多

大致题意:
    一个书架共有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;
}
 
0
0
分享到:
评论

相关推荐

    ZOJ:浙江大学程序在线评测系统.docx

    ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...

    zoj 1002_zoj1002_

    ZOJ 1002的具体内容未知,但常见的ACM题目类型包括但不限于:排序与查找、图论、动态规划、贪心算法、数学问题、字符串处理等。因此,这个C++程序可能涉及以上某一种或多种算法的组合。 C++语言在编程竞赛中广泛...

    zoj 700源代码

    3. **字符串处理**:ZOJ题目中往往包含许多字符串处理问题,如模式匹配、字符串比较、最长公共子序列等。源代码会展示如何高效地操作字符串。 4. **数学知识**:部分题目可能需要运用到高等数学知识,如组合数学、...

    zoj1027解题指南

    在算法竞赛中,字符串处理是一个常见的主题,可能涉及到的操作包括但不限于编辑距离(Levenshtein Distance)、最长公共子序列(Longest Common Subsequence)或者其他的字符串匹配算法。"求串相似度"通常是指计算两...

    zoj 源码700题

    【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...

    zoj.zip_zoj

    4. **动态规划**:背包问题、最长公共子序列、最短路径、最长上升子序列等,动态规划能有效地解决具有重叠子问题和最优子结构的复杂问题。 5. **图论**:最小生成树(Prim 或 Kruskal 算法)、最短路径(Floyd-...

    ZOJ月赛 题解 (ZOJ Monthly, August 2014)

    3. **动态规划(DP)**:动态规划是一种强大的问题解决方法,适用于解决最优决策问题,如背包问题、最长公共子序列、矩阵链乘法等。解题报告中的DP思路通常包括状态定义、状态转移方程和边界条件。 4. **贪心算法**...

    ZOJ题目答案源码

    例如,动态规划在解决背包问题、最长公共子序列、最小编辑距离等问题上有着广泛的应用;图论则涉及到最短路径算法(Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法)等。 此外,源码中...

    zoj代码集合

    DP在解决复杂问题时有着广泛的应用,例如背包问题、最长公共子序列、最短路径等。代码集可能会包含各种类型的DP模板和实例解析。 3. **贪心算法**:贪心策略通常用于求解局部最优解的问题,如活动选择问题、霍夫曼...

    zoj-cpp.zip_zoj

    在编程竞赛和算法设计中,动态规划经常被用来解决如背包问题、最长公共子序列、最短路径等经典问题。动态规划的核心思想是记忆化,避免重复计算,以提高效率。 在学习和使用这个压缩包时,初学者可以从以下几个方面...

    zoj 题库 详细解答 解题代码

    zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...

    zoj.rar_zoj_zoj4041

    《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...

    Problem Arrangement zoj 3777

    Problem Arrangement zoj 3777

    浙江大学ZOJ题目分类

    浙江大学ZOJ(Zhejiang University Online Judge)是一个在线编程练习平台,主要服务于计算机科学和技术的学习者,特别是对算法和编程有浓厚兴趣的学生。这个平台提供了大量的编程题目,涵盖了各种难度和主题,帮助...

    ACM训练必备POJ ZOJ题目分类及解题思路

    学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路

    ZOJ题解集合-截至2835

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...

    zheda.rar_zoj

    3. **字符串处理**:ZOJ中的许多题目涉及到字符串操作,如模式匹配、字符串比较、最长公共子序列等。掌握字符串处理技巧对解题至关重要。 4. **数学应用**:部分题目需要运用到离散数学、组合数学、数论等领域的...

    zoj.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar

    标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...

    ZOJ1003 Crashing Balloon

    【ZOJ1003 Crashing Balloon】这个问题是一个经典的计算机科学竞赛编程题目,主要涉及动态规划(Dynamic Programming, DP)和贪心算法(Greedy Algorithm)的知识点。在这个问题中,参赛者需要编写程序来模拟气球...

Global site tag (gtag.js) - Google Analytics