223

# 题目

Description

1行: M，S和C(用空格分开)
2到C+1行:每行包含一个整数，表示牛所占的牛棚的编号。

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

25

# 题解

## 动态规划

dp(i,j) 表示前i个牛栏使用j个木板所需要的最小木板总长度

• 用一块新的木板 dp(i-1,j-1)+1
• 延长上一块木板 dp(i-1,j)+a[i]-a[i-1]

dp(k,0) (k!=0) 表示没有木板的情况下,拦住k个有牛的牛栏,应该是无穷大

dp(i,j) = \left\{\begin{matrix} 0 & i=0\\ INF & i \neq 0,j=0\\ min(dp(i-1,j-1)+1,dp(i-1,j)+a[i]-a[i-1]) & 其他 \end{matrix}\right. \${% endraw %} # 代码 ## 贪心 {% fold 点击显/隐代码 %}cpp 修理牛棚(贪心) https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 /*/ #define debug #include //*/ #include #include #include #include using namespace std; const int maxn = 205; int a[maxn], b[maxn]; int m, s, c; int main() { #ifdef debug freopen("in.txt", "r", stdin); int START = clock(); #endif cin.tie(0); cin.sync_with_stdio(false); while (cin >> m >> s >> c) { for (int i = 0; i < c; i++) cin >> a[i]; sort(a,a+c); if (c == 0 || m >= c ) { cout << c << endl; } else { for (int i = 0; i < c - 1; i++) b[i] = a[i + 1] - a[i] - 1; sort(b, b + c - 1); int ans = a[c - 1] - a[0] + 1; // cout< //*/ #include #include #include #include using namespace std; const int maxn = 205; const int INF = 0x3f3f3f; int a[maxn]; int m, s, c; int dp[maxn][maxn]; int main() { #ifdef debug freopen("in.txt", "r", stdin); int START = clock(); #endif cin.tie(0); cin.sync_with_stdio(false); a[0] = 0; while (cin >> m >> s >> c) { for (int i = 1; i <= c; i++) { cin >> a[i]; } sort(a + 1, a + 1 + c); for (int i = 0; i <= c; i++) dp[i][0] = INF; memset(dp[0], 0, sizeof(dp[0])); for (int i = 1; i <= c; i++) for (int j = 1; j <= m; j++) dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + a[i] - a[i - 1]); cout << dp[c][m] << endl; // for (int i = 0; i <= c; i++){ // for (int j = 0; j <= m; j++) // printf("%5d ",dp[i][j]); // printf("\n"); // } } #ifdef debug printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC); #endif return 0; } 

• 点击查看/关闭被识别为广告的评论