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

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