$P5017 摆渡车$

problem
毒瘤$DP$
#ifdef Dubug

#endif

#include <bits/stdc++.h>

using namespace std;

typedef long long LL ;

inline LL In() { LL res(0),f(1); register char c ;

	while(isspace(c=getchar())) ; c == '-'? f = -1 , c = getchar() : 0 ;

	while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(c=getchar())) ;

	return res * f ;

}

int n , m ;

const int N = 500 + 5 ;

const int M = 100 + 5 ;

int t[N] , res[N] ;

int dp[N][M] ;

signed main() {

	memset(dp,0x7f,sizeof(dp)) ;

	n = In() , m = In() ;

	for(register int i=1;i<=n;i++) t[i] = In() ;

	sort(t+1 , t+n+1) ;

	for(register int i=1;i<=n;i++) res[i] = res[i-1] + t[i] ;

	t[0] = -0x7f7f7f7f , dp[0][0] = 0 ;

	for(register int i=0;i<=n;i++) {

		int Min = min(t[i+1]-t[i] , m-1) ;

		for(register int j=0;j<=Min;j++)

			if(dp[i][j] != 0x7f7f7f7f)

				for(register int k=1;k+i<=n;k++) {

					int Max = max(t[i]+j+m-t[i+k] , 0) ;

					dp[i+k][Max] = min(dp[i+k][Max] , dp[i][j] + (Max + t[i+k]) * k-(res[i + k] - res[i])) ;

				}

	}

	int ans = 0x7f7f7f7f ;

	for(register int i=0;i<m;i++) ans = min(dp[n][i] , ans) ;

	cout << ans << endl ;

	return 0 ;

}
巴特西

$P5017 摆渡车$

最新文章

热门文章
