謎のWAると心が折れそうになる。1行目の石が0の時を考慮していなかった。こういう見落としパチモンの時もあったけどデバグに時間掛かりすぎてヤバイ。
#include <iostream> #include <vector> #include <cstdlib> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main(){ int n , m; while(cin >> n >> m , n ){ int pos[151][10] ={0}; int rate[151][10] = {0}; int cnt[151] = {0}; for(int i = 1 ; i <= n ;i++){ int k; cin >> k; cnt[i] = k; rep(j,k){ cin >> pos[i][j] >> rate[i][j]; } } n++; int dp[152][10][80] = {0}; rep(i,151)rep(j,10)rep(k,80)dp[i][j][k] = (1<<29); rep(j,10)rep(k,80)dp[0][j][k] = 0; rep(j,10)rate[0][j] = 0; cnt[0] = 1; for(int k = m ; k>=0 ; k--){ for(int i = 1;i<n;i++){ rep(prev,cnt[i-1]){ rep(cur,cnt[i]){ if(i-1){ dp[i][cur][k] = min( dp[i][cur][k], dp[i-1][prev][k] + (rate[i][cur]+rate[i-1][prev]) * abs( pos[i][cur] - pos[i-1][prev] ) ); }else{ dp[i][cur][k] = 0; } } } } if(k){ for(int i=2;i<n;i++){ rep(prev,cnt[i-2]){ rep(cur,cnt[i]){ if(i-2){ dp[i][cur][k-1] = min( dp[i][cur][k-1] , dp[i-2][prev][k] + (rate[i][cur]+rate[i-2][prev]) * abs( pos[i][cur] - pos[i-2][prev] ) ); }else{ dp[i][cur][k-1] = 0; } } } } } } int ret = (1<<29); rep(k,m+1){ if(k)rep(i,cnt[n-2])ret = min(ret,dp[n-2][i][k]); rep(i,cnt[n-1])ret = min(ret,dp[n-1][i][k]); } cout << ret << endl; break; } }