dp~~~
/*ID: LeongHouHengPROG: barn1LANG: C++ */ #include <iostream> #include <memory.h> #include <string.h> #include <fstream> #include <algorithm> using namespace std; ifstream fin("barn1.in"); ofstream fout("barn1.out"); int cows[201]; int dp[250][60]; int MIN_NUM = 2e9; int main(){ int M, S, C; fin >> M >> S >> C; for(int i = 0; i < C; i++){ fin >> cows[i]; } sort(cows, cows+C); memset(dp, 0x1f, sizeof(dp)); dp[0][0] = 1; for(int i = 1; i < C; i++){ for(int j = 0; j <= i && j < M; j++){ dp[i][j] = dp[i-1][j] + (cows[i] - cows[i-1]); if(j > 0) dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1); if(C-1 == i) MIN_NUM = min(MIN_NUM, dp[i][j]); } } fout << MIN_NUM << endl; }新聞熱點
疑難解答
