INC 2010

Soal I Maximum Sum in Matrix

Soal ini bisa diselesaikan pake Dynamic Programming dengan state(n,m,k) artinya nilai maksimum sampai baris ke n, dimana sekarang ambil kolom m dan masih bisa k kali ubah.
Kode gua sempet ilang gara – gara gua execute dari command line dengan i < i.in > i.cpp untung Suhendry masih menyimpan jawaban gua 🙂

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int num[100][100],sum[100][100];
int best[100][100][100];
int n,m;

int calc(int nn, int mm,int kk)
{
  if (nn >= n) return 0;
  if ( kk == 0 ) return sum[nn][mm];
  if (best[nn][mm][kk] == -1)
  {
    int res = -1;
    for (int i = 0 ; i < m;i++) res = max(res, num[nn][i] + calc(nn+1,i, kk - (mm!=i)));
    best[nn][mm][kk] = res;
  }
  return best[nn][mm][kk];
}

int main()
{
  int t,k;
  scanf("%d",&t);
  while (t--)
  {
    scanf("%d %d %d",&n,&m,&k);
    memset(best,-1,sizeof(best));
    for(int i = 0 ; i< n;i++)
      for(int j = 0;j<m;j++)
        scanf("%d",&num[i][j]);

    for(int i = n-1;i>=0;i--)
      for(int j = 0 ;j<m;j++)
        if(i==n-1) sum[i][j] = num[i][j];
        else sum[i][j] = sum[i+1][j] + num[i][j];
    int ret = -1;
    for(int i = 0 ;i<m;i++) ret >?= calc(0,i,k);
    printf("%d\n",ret);
  }
  return 0;
}

Iklan

8 comments on “INC 2010

  1. @su : punya gua pre-order kok buat traverse node nya, misal A punya anak B,C trus B punya anak D, E tar punya gua jadiin sequence A,B,D,E,C

    @felix : eh iya nih, yang C juga pada ilang2, padahal cara post code nya pake tag yang sama, btr gua benerin

    Suka

  2. Ping-balik: 2010 in review | Marcadian's Blog

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s