程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Ural 1167 Bicolored Horses (DP)

Ural 1167 Bicolored Horses (DP)

編輯：C++入門知識

Ural 1167 Bicolored Horses (DP)


題目地址：Ural 1167

感覺這題的思路類似於背包的做法。。

先預處理出來每個馬與之前所有的馬的0的數量和1的數量，用數組a[0][i]和a[1][i]來表示。

然後再用數組dp[i][j]來表示當前第i個馬槽最右端為第j個馬時的最小值。

dp的時候先枚舉馬槽，再用n*n枚舉當前的馬槽要選用的馬的區間。這樣總時間復雜度是O(n*n*k)。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int INF=0x3f3f3f3f;
#define LL long long
int a[3][600], dp[600][600], c[600];
int main()
{
    int n, k, i, j, x, h;
    c[0]=0;
    scanf("%d%d",&n,&k);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&c[i]);
    }
    a[0][0]=0;
    a[1][0]=0;
    for(i=1; i<=n; i++)
    {
        a[0][i]=c[i]==0?a[0][i-1]+1:a[0][i-1];
        a[1][i]=c[i]==1?a[1][i-1]+1:a[1][i-1];
    }
    memset(dp,INF,sizeof(dp));
    dp[0][0]=0;
    for(i=1;i<=k;i++)
    {
        for(j=1;j<=n;j++)
        {
            for(h=0;h
  1. 上一頁:
  2. 下一頁:
C++入門知識
如何實現給一個結構體隊列分配內存空間

如何實現給一個結構體隊列分配內存空間 1、主要功能 對
openCV學習記錄：濾鏡：線條&amp;素描

openCV學習記錄：濾鏡：線條&素描 線條濾鏡
經典：教你理解復雜的C/C++聲明

  介紹  曾經碰到過讓你迷惑不
C++基礎之析構函數的介紹

  析構函數(destructor)
POJ 2312 Battle City(優先隊列+BFS)

POJ 2312 Battle City(優先隊列+BFS)
BNUOJ34977夜空中最亮的星（數學，向量的應用）

BNUOJ34977夜空中最亮的星（數學，向量的應用）

相關文章
閱讀排行榜
Go語言實現跳表(SkipList) opaque struct——c/c++如何隱藏內部結構體的定義？ HDU 4351 c++11之初始化列表 實驗12：Problem C: 重載字符的加減法，problem加減法 CodeForces 358E - Dima and Kicks ZOJ1074 (最大和子矩陣 DP)，zoj1074dp 直接選擇排序 hdu3275 Light很好很好的線段樹收獲豐富 九度教程第64題 mfc實現播放器功能，雙擊全屏，再雙擊還原
熱門圖文
Spring JDBC抽象框架簡化Web數據庫開發 優化php效率,提高php性能的一些方法 PHP函數spl_autoload_register()用法和__autoload()介紹 PHP生成制作驗證碼，php生成驗證碼 C++的EXIT與析構函數 uva 1471 Defense Lines (降低復雜度) hibernate annoation (八 關聯映射) C#保存文件對話框(SaveFileDialog)（1）
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved