【USACO】Barn Repair

2019-11-14 09:41:02

字体：大中小

来源：转载

供稿：网友

PRoblem here

Solution

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; }

上一篇：Cogs 58. 延绵的山峰(st表)

下一篇：【Python】学习笔记——-5、第一个Python程序