範例程式碼 uva1632

//uva1632
#include<stdio.h>
#include<stdlib.h>
#include <algorithm>

int a[10010],  b[10010],  d[10010][10010][2];

int main(void) {
	int i, j, k, n, cur, minv;
	while(scanf("%d", &n) == 1) {
		for(i = 1; i <= n; i++)
			scanf("%d%d", &a[i], &b[i]);
		
		for(i = 0; i <= n; i++)
			for(j = 0; j <= n; j++)
				d[i][j][0] = d[i][j][1] = (1 << 30);				
		for(i = 1; i <= n; i++)
			d[i][i][0] = d[i][i][1] = 0;			
		for(i = n; i > 0; i--) {
			for(j = i + 1; j <= n; j++) {
				d[i][j][0] = std::min(d[i + 1][j][0] + a[i + 1] - a[i], d[i + 1][j][1] + a[j] - a[i]);
				if(d[i][j][0] >= b[i])
					d[i][j][0] = (1 << 30);
				d[i][j][1] = std::min(d[i][j - 1][0] + a[j] - a[i], d[i][j - 1][1] + a[j] - a[j - 1]);
				if(d[i][j][1] >= b[j])
					d[i][j][1] = (1 << 30);					
			}
		}
		minv = std::min(d[1][n][0], d[1][n][1]);
		if(minv == (1 << 30))
			printf("No solution\n");
		else
			printf("%d\n", minv);
	}
	return 0;
}