T1 题目

题目描述

若

$$a_1 + a_2 + a_3 + \cdots + a_k = n \quad (1 \le k \le n) $$

求

$$\prod_{i=1}^{k} a_i$$

的最大值。

---

输入格式

第一行输入整数

$$T \quad (1 \le T \le 10^4)$$

表示测试组数。

接下来 $T$ 行，每行输入一个整数 $n$。

---

输出格式

输出 $T$ 行。

每行输出最大乘积

$$\prod_{i=1}^{k} a_i \bmod 10^9$$

---

数据范围

• 40% 数据：$1 \le n \le 50$

• 所有数据：$1 \le n \le 10^6$

---

题解

这是一个非常经典的问题：

整数拆分最大乘积

即：

把 $n$ 拆成若干正整数，使乘积最大。

---

40 分 DP / 完全背包做法

因为 $n \le 50$，每次 $O(n^2)$ 就够了。

40 分做法可用完全背包。设 $dp[i]$ 表示和为 $i$ 时的最大乘积。把每个正整数 $x$ 看作一种可无限选取的物品，体积为 $x$，收益为乘法因子 $x$。转移为

$$dp[s]=\max(dp[s],dp[s-x]\times x)$$

初值 $dp[0]=1$，最终输出 $dp[n]$。

把每个正整数 $x$ 看成一种“物品”：

• 体积 = $x$

• 价值不是加法，而是乘法中的一个因子 $x$

我们希望选若干个物品，使总体积恰好为 $n$，并让这些数的乘积最大。

因为每个数可以取任意次，所以这本质上就是完全背包。这就是一个“恰好装满”的完全背包，只不过普通背包是“价值相加”，这里变成了“乘积最大”。

如果直接这样写，那么对于 $n=2$：

• 不拆：2

• 拆：1+1，乘积 1

题目要求是“若 $a_1+\cdots+a_k=n$, $1\le k\le n$”
其实是允许 $k=1$ 的，也就是允许不拆。

那么最终答案就是：

$$dp[n]$$

并且转移时把 $j=i$ 也允许即可。

---

代码（完全背包写法）

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 1e9;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;

    while(T--)
    {
        int n;
        cin >> n;

        ll dp[55];
        for(int i = 0; i <= n; i++) dp[i] = 0;

        dp[0] = 1;

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                dp[i] = max(dp[i], dp[i - j] * j);
            }
        }

        cout << dp[n] % mod << "\n";
    }

    return 0;
}

为什么这就是完全背包

因为：

• 每个整数 $x$ 都可以选很多次

• 每次选一个 $x$，就相当于消耗容量 $x$

• 最终总和恰好要到 $n$

这和完全背包“每种物品无限件”完全一致。

只不过普通背包是：

$$dp[s]=\max(dp[s],dp[s-x]+v)$$

这题变成：

$$dp[s]=\max(dp[s],dp[s-x]\times x)$$

所以本质没变，只是“加法价值”换成了“乘法价值”。

复杂度

每组数据：

$$O(n^2)$$

在 $n \le 50$ 时非常轻松。

满分做法

最优策略是：

尽量拆成 3

至于为什么，证明可以去以下这篇文章去看

数学结论：

当 $n ≥ 5$ 时

$$3 \times (n-3) > n$$

说明拆出 3 会更优。

---

分类讨论

情况1：n % 3 = 0

全部拆成3

$$3^{n/3}$$

---

情况2：n % 3 = 1

例如：

10 = 3 + 3 + 3 + 1

但

3 + 1 = 4

更优：

3 + 3 + 4

所以

$$3^{(n/3-1)} \times 4$$

---

情况3：n % 3 = 2

直接多一个2

$$3^{n/3} \times 2$$

---

特殊情况

n = 1 → 1  
n = 2 → 1  
n = 3 → 2

---

时间复杂度

每个查询

$$O(\log n)$$

快速幂即可。

---

T1 参考代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 1e9;

ll ksm(ll a,ll b)
{
    ll r = 1;
    while(b)
    {
        if(b&1) r = r * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;

    while(T--)
    {
        ll n;
        cin >> n;

        if(n==1) cout<<1<<"\n";
        else if(n==2) cout<<2<<"\n";
        else if(n==3) cout<<3<<"\n";
        else
        {
            ll a = n/3;
            ll b = n%3;

            if(b==0)
                cout<<ksm(3,a)<<"\n";
            else if(b==1)
                cout<<ksm(3,a-1)*4%mod<<"\n";
            else
                cout<<ksm(3,a)*2%mod<<"\n";
        }
    }
}

---

T2 题目

题目描述

有 $n$ 个城市，编号 $1 \sim n$。

有 $m$ 条无向公路。

每条公路有：

• 费用 $w_i$

• 风景好看度 $b_i$

汽车要从 1 号城市到 n 号城市。

规则：

可以 免去路径上一条风景好看度最高的公路费用
（如果有多条同样最高，只能免去一条）。

求 最小总费用。

若无法到达，输出

-1

---

输入格式

第一行

n m

接下来 $m$ 行

u v w_i b_i

表示一条连接 $u,v$ 的无向边

• 费用 $w_i$

• 风景值 $b_i$

---

输出格式

输出从 $1$ 到 $n$ 的最小费用。

---

数据范围

$$1 \le n,m \le 5000$$ $$1 \le w_i,b_i \le 10^9$$

---

T2 题解

这题难点不在最短路本身，而在于：

“免费边不是任意边，而是必须来自路径上的最高风景值层”

所以最自然的处理方式不是“最后减一条边”，而是：

先确定哪条边是免费边
再围绕这条边重建整条路径

这样约束就干净了。

---

枚举哪条边 $e=(u,v,w,b)$ 被免费。若该边可被免费，则整条路径中所有边都必须满足风景值不超过 $b$，且路径必须经过边 $e$。于是合法路径只可能形如

$$1\to u \to v \to n$$

或

$$1\to v \to u \to n$$

其中中间的边 $e$ 免费，因此代价分别为

$$\operatorname{dist}_b(1,u)+\operatorname{dist}_b(v,n) $$

和

$$\operatorname{dist}_b(1,v)+\operatorname{dist}_b(u,n) $$

这里 $\operatorname{dist}_b(x,y)$ 表示只使用满足风景值 $\le b$ 的边时的最短路。将边按 $b$ 升序排序并分组加入图，对每个 $b$ 值跑两次 Dijkstra，即可处理该组所有边。

---

复杂度

每个不同 b 值：2 × Dijkstra

最坏情况：$O(m^2 log n)$,在$n,m ≤ 5000$范围内可通过。

T2 代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5005;
const ll inf = (ll)4e18;

struct Ed{
    int u,v;
    ll w,b;
};

int n,m;
Ed a[5005];

vector<pair<int,ll>> g[N];

ll d1[N],dn[N];
bool vis[N];

void dij(int s,ll dis[])
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=inf;
        vis[i]=0;
    }

    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;

    dis[s]=0;
    q.push({0,s});

    while(!q.empty())
    {
        auto t=q.top();
        q.pop();

        int u=t.second;
        if(vis[u]) continue;
        vis[u]=1;

        for(auto e:g[u])
        {
            int v=e.first;
            ll w=e.second;

            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
}

bool cmp(Ed x,Ed y)
{
    return x.b<y.b;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        cin>>a[i].u>>a[i].v>>a[i].w>>a[i].b;
    }

    sort(a+1,a+m+1,cmp);

    ll ans=inf;

    int i=1;

    while(i<=m)
    {
        int j=i;

        while(j<=m && a[j].b==a[i].b) j++;

        for(int k=i;k<j;k++)
        {
            int u=a[k].u;
            int v=a[k].v;
            ll w=a[k].w;

            g[u].push_back({v,w});
            g[v].push_back({u,w});
        }

        dij(1,d1);
        dij(n,dn);

        for(int k=i;k<j;k++)
        {
            int u=a[k].u;
            int v=a[k].v;

            if(d1[u]!=inf && dn[v]!=inf)
                ans=min(ans,d1[u]+dn[v]);

            if(d1[v]!=inf && dn[u]!=inf)
                ans=min(ans,d1[v]+dn[u]);
        }

        i=j;
    }

    if(ans==inf) cout<<-1<<"\n";
    else cout<<ans<<"\n";

    return 0;
}