2023牛客寒假算法基础集训营5-L-小沙の抱团 hard

Solost

2023 年 02 月 02 日

354 次浏览

暂无评论

1066字数

题目题解

![](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/02/02/image%281%29.png)

## solution

* 因为找最小代价，所以初始化数组为最大
* 我们可以很快得知，最大状态也就是n的代价是固定的，最小代价不确定，所以我们从大到小推
* 我们用一维数组来dp,f[i]代表从n到达i时的代价。
* 那么转移方程就是`f[i - i % v[j]] = min(f[i - i % v[j], f[i] + w[i]]`,反推比较好推出来，否则正推对应情况有点多。

~~~cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
    memset(f, 0x3f, sizeof f);
    cin >> n >> m;

for (int i = 1; i <= m; i++) {
        cin >> w[i] >> v[i];
    }
  
    memset(f, 0x3f, sizeof f);
    f[n] = 0;
    for(int i = n; i >= 0; i--){
    	if(f[i] == INF) continue;
    	for(int j = 1; j <= m; j++){
    		if(i < v[j]) continue;
    		f[i - i % v[j]] = min(f[i - i % v[j]], f[i] + w[j]);
    	}
    }
    int i = 1;
    while(f[i] == INF) i++;
    cout << f[i];
    return 0;
}
~~~

最后修改：2023 年 02 月 02 日