```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
long long value[m], mess[m], t;
for (int i = 0; i < m; i++)
{
cin >> mess[i] >> t;
value[i] = mess[i] * t;
}
long long ts[n + 1] = {};
for (int j = 0; j < m; j++)
{
for (int i = n ; i >= 1; i--)//1
{
if (mess[j] <= i)
ts[i] = max(ts[i - mess[j]] + value[j], ts[i]);//2
}
}
cout << ts[n];//3
}
```
by Tim0509 @ 2023-11-23 22:16:44
`ts[i] = max(ts[i - mess[j]] + value[j], ts[i]);//并非i-1`
by Tim0509 @ 2023-11-23 22:17:19
确实是状态更新的错误。状态转移方程中max函数是限制当前状态是否更新的,与上一个状态没有关系。这里混淆了子问题,非常感谢你的帮助。
by dps2019 @ 2023-11-23 22:34:28