C++实现
时间: 2023-07-11 08:12:46 浏览: 49
好的,以下是C++的实现代码:
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;
const int MAXM = 1005;
int n, m;
int a[MAXN], s[MAXN];
int dp[MAXN][MAXM];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = a[i];
}
sort(s + 1, s + n + 1);
memset(dp, -INF, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= a[i]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + s[i]);
}
}
}
if (dp[n][m] < 0) {
cout << "-1\n";
} else {
cout << accumulate(a + 1, a + n + 1, 0) - dp[n][m] << "\n";
}
return 0;
}
```
其中,我们使用了 STL 中的 accumulate 函数来计算剩余卡牌点数之和。
时间复杂度为 O(nm)。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)