Ural 1167 Bicolored Horses (DP) - c++编程基础

TOP

Ural 1167 Bicolored Horses (DP)

2015-07-20 17:32:42 来源: 作者: 【大中小】浏览:2次

Tags：Ural 1167 Bicolored Horses

题目地址：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


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：BZOJ 1014 JSOI 2008 火星人prefi..	下一篇：HDU 2255 奔小康赚大钱 KM裸题

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: