题解：P1060 [NOIP2006 普及组] 开心的金明

· · 题解

洛谷P1060

本题是一个典型的 01 背包问题，可转化为每个物品的重量 v_i ，价值为 v_i\times w_i ，背包总容量为 N 。

设 f_{i,j} 表示当处理到第 i 件物品时，还有 j 的空间时所获的的价值（第 i 件物品可以选择取或者不取），可得状态转移方程：

f_{i,j}=\min(f[i-1][j],f[i-1][j-vj]+v_i\times w_i)

再用滚动数组优化空间，时间复杂度为 O(N^2) ，空间复杂度为 O(N) 。

完结散花！

#include <bits/stdc++.h>
using namespace std;
int f[30001],v[26],w[26],n,m;
int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>v[i]>>w[i];
    }
    for (int i=1;i<=m;i++){
        for (int j=n;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+v[i]*w[i]);
        }
    }
    cout<<f[n]<<endl;
    return 0;
}
\begin{aligned}\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)&=\sum_{i=1}^n\sum_{j=1}^n\sum_{d\mid\gcd(i,j)}\varphi(d)\\&=\sum_{d=1}^n\varphi(d)\sum_{i=1}^n\sum_{j=1}^n[d\mid\gcd(i,j)]\\&=\sum_{d=1}^n\varphi(d)\sum_{i=1}^n\sum_{j=1}^n[d\mid i][d\mid j]\\&=\sum_{d=1}^n\varphi(d){\left\lfloor \frac{n}{d}\right\rfloor}^2\end{aligned}