URAL 1167. Bicolored Horses(DP)

제목 링크
2차원 DP, 두 개의 태그 그룹을 열어 앞의 i 개수 1의 개수와 0의 개수를 기록합니다.1Y.
상태 이동 방정식: p[i][j]=min(p[i-k][j-1]+(sum1(i)-sum1(i-k))*(sum0(i)-sum0(i-k))))(처음에는 i-k가 k라고 생각했어요. 자기가 몇 개의 데이터를 시도해 봤는데 계산이 틀렸어요)

 1 #include <stdio.h>

 2 #include <string.h>

 3 #define N 10000000

 4 int p[501][501],sum1[501],sum0[501];

 5 int main()

 6 {

 7     int n,m,i,j,k;

 8     scanf("%d%d",&n,&m);

 9     for(i = 1;i <= n;i ++)

10     {

11         scanf("%d",&j);

12         if(j == 1)

13         {

14             sum1[i] = sum1[i-1]+1;

15             sum0[i] = sum0[i-1];

16         }

17         else

18         {

19             sum0[i] = sum0[i-1]+1;

20             sum1[i] = sum1[i-1];

21         }

22     }

23     for(i = 1;i <= n;i ++)

24     {

25         for(j = 1;j <= m;j ++)

26         p[i][j] = N;

27     }

28     for(i = 1;i <= n;i ++)

29     {

30         p[i][1] = sum1[i]*sum0[i];

31     }

32     for(i = 1;i <= n;i ++)

33     {

34         for(j = 2;j <= m&&j <= i;j ++)

35         {

36             for(k = 1;k <= i&&i-k>=j-1;k ++)

37             {

38                if(p[i][j] > p[i-k][j-1]+(sum1[i]-sum1[i-k])*(sum0[i]-sum0[i-k]))

39                p[i][j] =  p[i-k][j-1]+(sum1[i]-sum1[i-k])*(sum0[i]-sum0[i-k]);

40             }

41         }

42     }

43     printf("%d
",p[n][m]);

44     return 0;

45 }