首页 > 其他 > 详细

NOI-动规题目集锦

时间:2019-09-06 20:44:05      阅读:156      评论:0      收藏:0      [点我收藏+]

 

162:Post Office

解题思路

技术分享图片
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1001],f[500][500],mi[500][500],i,j;
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            f[i][j]=9999999;//赋为最大值
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++) mi[i][j]=mi[i][j-1]+a[j]-a[(i+j)/2];//从第i个村庄到第j个村庄中只建一个邮局的总路径长度 
        f[i][1]=mi[1][i];//转移到f 
    }
    for(i=2;i<=n;i++)
        for(j=2;j<=m;j++)
            for(int k=j-1;k<i;k++)
                f[i][j]=min(f[i][j],f[k][j-1]+mi[k+1][i]);
    cout<<f[n][m]<<endl;
    return 0;
}
View Code

1759:最长上升子序列

技术分享图片
#include<iostream> 
#include<cstring>
using namespace std;
const int N = 1050;
int a[N],f[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)f[i]=1;
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(a[j]<a[i])f[i]=max(f[i],f[j]+1);
        }
    }
    int ans = 1;
    for(int i=0;i<n;i++)ans = max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}
View Code

 

NOI-动规题目集锦

原文:https://www.cnblogs.com/yun-an/p/11477893.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!