题解 | #[NOIP2006]开心的金明#

比较疑惑的是这一点主要是

#include "iostream"
#include "algorithm"
using namespace std;
int V[26];
int W[26];
long long int dp[26][30001];
int main()
{
    int N,n,i,x;
    cin>>N>>n;
    for(i=1;i<=n;i++){
        cin>>V[i]>>W[i];
    }
    for(i=1;i<=n;i++){
        for(int j=N;j>=1;j--)
        {
            if(V[i]>j) 要思考的是一般来说都是倒着排序的    {
                dp[i][j]=dp[i-1][j];
            }else dp[i][j]=max(dp[i-1][j],dp[i-1][j-V[i]]+V[i]*W[i]);
        }
    }
    cout<<dp[n][N];
}
这里学到了比较新的东西

``` js


是的，你完全正确。在背包问题中，当我们使用map（或unordered_map）来存储动态规划的状态时，我们实际上是在实现一种离散化的过程。离散化是一种数据预处理技术，用于将大范围的数值映射到较小的、连续的范围内，以便更有效地存储和计算。

在背包问题中，背包的容量通常是一个较大的整数范围，但如果不是所有的容量都会被实际使用到（即，不是所有的物品组合都会导致每个可能的容量被访问），那么使用数组来存储DP状态将会非常浪费空间。而map（或unordered_map）则提供了一种按需分配空间的方式。

具体来说，当我们尝试更新一个背包容量为j的状态时，我们首先检查dp[j]是否已经被创建。如果j还没有被访问过，那么dp[j]在map中就不存在，此时我们可以安全地创建一个新的键值对来存储这个状态。如果j已经被访问过，那么dp[j]已经在map中存在，我们可以直接更新它的值。

这种方式的好处是，我们只为实际使用到的背包容量分配了空间，从而大大减少了内存的使用。同时，由于map内部使用了红黑树（对于map）或哈希表（对于unordered_map）来存储键值对，查找和更新操作的时间复杂度都是对数级别或接近常数级别的，因此效率也是可以接受的。

总结来说，使用map（或unordered_map）来实现背包问题的DP状态存储，不仅实现了离散化，减少了空间的使用，而且保持了较高的时间效率。