3059440_ac_140ms_7988k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 52 行

#include "stdio.h"
#define size 1001
int cost, n;
int value[ size ][ size ];
int ans[ size ][ size ];

int solve(){
	int i, j, k, min;

	if ( scanf("%d", &cost ) == EOF ) return 0;
	scanf("%d", &n );

	for ( i = 1; i <= n; i++ ){
		for ( j = i; j <= n; j++ ){
			scanf("%d", &value[ i ][ j ] );
		}
	}

	for ( i = 1; i <= n; i++ ){
		ans[ 1 ][ i ] = cost + value[ 1 ][ i ] ;
	}

	for ( i = 2; i <= n; i++ ){
		min = 100000000;
		for ( j = 1; j < i; j++ ){
			if ( ans[ j ][ i - 1 ] < min ){
				min = ans[ j ][ i - 1 ];
			}
		}
		for ( j = i; j <= n; j++ ){
			ans[ i ][ j ] = min + cost + value[ i ][ j ];
		}
	}
	
	min = 100000000;

	for ( i = 1; i <= n; i++ ){
		if ( ans[ i ][ n ] < min ){
			min = ans[ i ][ n ];
		}
	}

	printf("%d\n", min );

	return 1;
}

int main(){
	
	while( solve() );
	return 0;
}