torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Codeforces #186, D : Ilya and Roads

概要

重み付き区間が m 個与えられる。
この区間群から、一つ以上の区間によって被覆されている部分の長さが k 以上になるようにいくつかの区間を選ぶ。
このときの重みの総和の最小値を求めよ。

解法

dp[ 何番目まで考慮したか ][ 何箇所被覆したか ] := このときの重みの最小値
として動的計画法をすると答えが求まります。

初期状態は dp[ 0 ][ 0 ] = 0 で、状態遷移は次のようになります

  • dp[ i ][ j ] -> dp[ i + 1 ][ j ]
  • dp[ i ][ j ] から i 以降の各点に対し、最も軽い区間で被覆する遷移

コード

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int INF = INT_MAX;
const LL LINF = LLONG_MAX / 4;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, m, k;
	cin >> n >> m >> k;

	VVI G( n, VI( n, INF ) );
	REP( i, 0, m )
	{
		int l, r, c;
		cin >> l >> r >> c;
		l--;
		r--;

		REP( j, l, r + 1 )
		{
			G[j][r] = min( G[j][r], c );
		}
	}

	vector< vector<LL> > dp( n + 1, vector<LL>( n + 1, LINF ) );
	dp[0][0] = 0;
	REP( i, 0, n )
	{
		REP( j, 0, n )
		{
			dp[ i + 1 ][j] = min( dp[ i + 1 ][j], dp[i][j] );
			REP( k, i, n )
			{
				if ( G[i][k] == INF )
				{
					continue;
				}
				dp[ k + 1 ][ j + k - i + 1 ] = min( dp[ k + 1 ][ j + k - i + 1 ], dp[i][j] + G[i][k] );
			}
		}
	}

	LL res = LINF;
	REP( i, k, n + 1 )
	{
		res = min( res, dp.back()[i] );
	}

	cout << ( res == LINF ? -1 : res ) << endl;

	return 0;
}