dp凑数不重复c++代码
时间: 2023-10-02 20:07:04 浏览: 55
以下是使用动态规划解决凑数问题的 C++ 代码,确保不重复选取数值:
```C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
vector<int> coins(N);
for (int i = 0; i < N; i++) {
cin >> coins[i];
}
vector<int> dp(M + 1, 0);
dp[0] = 1;
for (int i = 0; i < N; i++) {
for (int j = M; j >= coins[i]; j--) {
dp[j] += dp[j - coins[i]];
}
}
cout << dp[M] << endl;
return 0;
}
```
其中,`N` 表示硬币的种类数,`M` 表示需要凑出的数值,`coins` 向量存储了每种硬币的面值,`dp` 向量记录了每个数值是否可以凑出。具体思路是,从第一个硬币开始,依次考虑每一种硬币能否凑出所有小于等于 `M` 的数值。如果能凑出,那么将 `dp[j-coins[i]]` 的值加到 `dp[j]` 上。最终,`dp[M]` 的值就表示能否凑出 `M` 这个数值。
相关问题
斜率优化dp代码实现c++
以下是斜率优化DP的C++代码实现,供您参考:
```c++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
ll dp[maxn], c[maxn], sum[maxn], h[maxn], q[maxn], n, m;
int head, tail;
int main()
{
scanf("%lld %lld", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &h[i]);
for(int i = 1; i <= n; i++) sum[i] = sum[i-1]+h[i];
head = tail = 1;
for(int i = 1; i <= n; i++)
{
while(head < tail && q[head+1] <= i) head++;
dp[i] = dp[q[head]] + (sum[i]-sum[q[head]]) - (i-q[head])*h[q[head]];
c[i] = h[i];
while(head < tail && (c[q[tail]]-c[q[tail-1]])*(i-q[tail]) >= (c[i]-c[q[tail]])*(q[tail]-q[tail-1])) tail--;
q[++tail] = i;
while(head < tail && (c[q[head+1]]-c[q[head]]) <= i*(h[q[head+1]]-h[q[head]])) head++;
}
printf("%lld\n", dp[n]*m);
return 0;
}
```
这段代码实现的是一道题目,使用了斜率优化DP。
用C++代码写一个区间dp的模板
以下是一个简单的区间dp的模板,使用C语言编写:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
int dp[MAXN][MAXN];
int main() {
int n;
scanf("%d", &n);
int a[MAXN];
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// 初始化dp数组
for (int i = 0; i < n; i++) {
dp[i][i] = a[i];
}
// 递推计算dp数组
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dp[i][j] = dp[i][i] + dp[i+1][j];
for (int k = i+1; k < j; k++) {
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
}
}
}
// 输出结果
printf("%d\n", dp[0][n-1]);
return 0;
}
```
这个模板可以用来解决一些区间dp问题,例如最长回文子序列、最大子段和等问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)