`
暴风雪
  • 浏览: 375044 次
  • 性别: 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
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics