大致题意:
一个书架共有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解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj吐血制作,希望大家喜欢
能AC 通过的c++代码,包括zoj1002,1091,1789
zoj 1002 C语言的为什么描述要这么多字啊。。