この問題は DP により解くことができます。

隣り合う板は同じ色に塗れないという条件があることから、最後に塗った板の色を状態に持つ必要がありそうです。そこで、\(\mathrm{DP}[i][j]\) を「板 \(i\) までの塗り方を決め、板 \(i\) を色 \(j\) で塗るときのコストの合計の最小値」とする DP を考えます。

遷移は \(\mathrm{DP}[i+1][j]=\min_{k\neq j}\mathrm{DP}[i][k]+C_{i+1,j}\) となります。

定義通り計算すると、 1 つの状態に \(\Theta(K)\) かかり、状態数は \(\Theta(NK)\) なので \(\Theta(NK^2)\) となり実行時間制限に間に合わせるのは困難です。

\(\min_{k\neq j}\mathrm{DP}[i][k]\) について考えます。「添字が \(j\) でないもののうち最小」は「全体で最小なものの添字が \(j\) でないなら全体で最小なもの」「全体で最小なものの添字が \(j\) なら全体で 2 番目に小さいもの」なので、いずれにせよ、全体で小さい方から 1 番目 2 番目のどちらかです。

よって \(i\) ごとにそれを予め \(O(K)\) ないし \(O(K\log K)\) かけて、最小値と小さい方から 2 番目の値を求めておくことで、遷移を \(O(1)\) 時間とすることができ、DP 全体を \(O(NK)\) ないし \(O(NK\log K)\) で求めることができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  vector<long long> dp(k);

  for(int i=0; i<n; i++){
    vector<long long> dp_sorted = dp;
    sort(dp_sorted.begin(), dp_sorted.end());
    vector<long long> new_dp(k);
    for(int j=0; j<k; j++){
      int c;
      cin >> c;
      if(dp[j] == dp_sorted[0]){
        new_dp[j] = dp_sorted[1] + c;
      }else{
        new_dp[j] = dp_sorted[0] + c;
      }
    }
    swap(dp, new_dp);
  }

  cout << *min_element(dp.begin(), dp.end()) << endl;
}

実装例 (Python)

N, K = map(int, input().split())
dp = [0]*K

for i in range(N):
  C = list(map(int, input().split()))
  dp_sorted = sorted(dp)
  new_dp = [0]*K
  for j, c in enumerate(C):
    if dp[j] == dp_sorted[0]:
      new_dp[j] = dp_sorted[1] + c
    else:
      new_dp[j] = dp_sorted[0] + c
  dp = new_dp

print(min(dp))