模拟赛P1042简单自信题

题目大意

有 $ n $  个箱子和 $ m $ 个小球,初始时第  $ i $ 个箱子有 $ a_i $​ 个小球。每次操作可以将一个小球移到相邻的箱子里。求要使得最终数组 $ a_i \ge a_{i+1} $的最小操作次数。

解题思路

设$ dp_{i,j,k} $ 为前 $ i $ 个箱子里一共放 $ j $ 个球,第 $ i $ 个箱子里放 $ k $ 个小球的代价。

我们先维护一个前缀和数组 $s_i$,然后在进行操作,例如:

原数组$ 5 \ 3 \ 2 \ 3 \ 3 \ 3 \ 3$

前缀和$ 5 \ 8 \ 10 \ 13 \ 16 \ 19 \ 21 $

显然我们要将第二个盒子的小球放入第三个小球中,更改后:

原数组$ 5 \ 2 \ 3 \ 3 \ 3 \ 3 \ 3$

前缀和$ 5 \ 7 \ 10 \ 13 \ 16 \ 19 \ 21$

我们可以发现,移动了小球后只有给出小球的一方前缀和会发生变化,其他则不受影响。因此,移动一个小球的代价即为 $ | s_i – j | $(即下标为 $ i $ 的箱子中的小球的前后变化的数量), $ j $ 的含义与上文相同。

怎么计算代价已经明了了,接下来就可以考虑状态转移方程了。

$$
dp_{i,j,k} = \min_{l=k}^m ( dp_{i,j,k} , dp_{i-1,j-k,l} + | s_i – j |)
$$

由于目的是构建非严格单调递减,所以 $ k \leq l \leq m $ ,这样子的时间复杂度是 $ O(NM^3) $ ,大概是可以过这一题的,但我们还可以进行进一步的优化。

我们可以发现在状态转移方程中有一个不变的量 $ | s_i – j | $ ,唯一变的量是 $ dp_{i-1,k,l} $ ,因为是找最小,所以我们只要提前维护好 $ dp_{i-j,k,l} $ 的最小值即可。时间复杂度为 $ O(NM^2) $

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(1)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <math.h>
using namespace std;
const int N=250+10;
int n,m;
int a[N],s[N];
int dp[2][N][N];//滚动数组节省内存
int g[2][N][N];
int ans;
inline int read(){
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        s[i]=s[i-1]+a[i];
    }
    memset(dp,0x3f,sizeof dp);
    for(int i=0;i<=m;i++)dp[0][0][i]=0;
    for(int i=1;i<=n;i++){
        int id=i&1;
        memset(dp[id],0x3f,sizeof dp[id]);
        memset(g[id],0x3f,sizeof g[id]);
        for(int j=0;j<=m;j++){
            for(int k=0;k<=j;k++){
                    dp[id][j][k]=g[id^1][j-k][k]+abs(s[i]-j);
            }
        }
        for(int j=0;j<=m;j++){
            for(int k=j;k>=0;k--){
                g[id][j][k]=min(g[id][j][k+1],dp[id][j][k]);
            }
        }
    }
    ans=0x3f3f3f3f;
    for(int i=0;i<=m;i++){
        ans=min(ans,dp[n&1][m][i]);
    }
    printf("%d",ans);
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇