P1877

HighPerformanceRobot · 2018-11-30 22:01:01 · 题解

音量调节

作为蒟蒻的我，一开始看到这题想的都是什么搜索，结果暴力打上去一看TLE四个点。。然后我作弊加了#pragma GCC optimize（3），最后MLE四个点，而且还是原来那四个TLE的点。啊啊啊，BFS都不能过，你们让不让人活？

好吧，暴力BFS的60分做法程序：

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int now,state;      //当前次数标记，当前音量值
    node(int a,int b)
    {
        now=a,state=b;
    }
};
queue <node> que;       //BFS队列
int beginlev,maxlev;    //初始音量，最大音量
int c[52];
int n,ans;
void bfs(int x)
{
    int step=que.front().now;       //标记当前的步数
    while(que.front().now==step)    //避免做过了头
    {
        if(que.front().state+x<=maxlev)
            que.push(node(que.front().now+1,que.front().state+x));
        if(que.front().state-x>=0)
            que.push(node(que.front().now+1,que.front().state-x));
        que.pop();
    }
}
void all()              //统计函数
{
    while(!que.empty())
        ans=max(ans,que.front().state),que.pop();
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>beginlev>>maxlev;
    que.push(node(1,beginlev));
    for(int i=0; i<n; i++)
        cin>>c[i];
    int i=0;
    while(!que.empty()&&i<n)
        bfs(c[i]),i++;
    all();
    if(ans)     //有修改过
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

然后就悲剧了。。

让我们再来研究一下，看看有没有可以优化的地方？

重点来了！

我们可以发现，这种BFS常常会有同样的状态，也就是同样的音量，然而在该批状态中（now相等的状态），同样的state（音量）是没用的。那怎么办？

我们可以开一个bool数组，判断当前的值是不是已经进入过队列了。

于是这题被轻松AC了。。

来来来stick code：

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int now,state;
    node(int a,int b)
    {
        now=a,state=b;
    }
};
queue <node> que;
int beginlev,maxlev;
int c[52];
int n,ans;
void bfs(int x)
{
    bool f[1001];
    int step=que.front().now;
    fill(f,f+maxlev+1,0);
    while(que.front().now==step)
    {
        if(que.front().state+x<=maxlev&&!f[que.front().state+x])
        {
            que.push(node(que.front().now+1,que.front().state+x));
            f[que.front().state+x]=1;
        }
        if(que.front().state-x>=0&&!f[que.front().state-x])
        {
            que.push(node(que.front().now+1,que.front().state-x));
            f[que.front().state-x]=1;
        }
        que.pop();
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>beginlev>>maxlev;
    que.push(node(1,beginlev));
    for(int i=0; i<n; i++)
        cin>>c[i];
    int i=0;
    while(!que.empty()&&i<n)
        bfs(c[i]),i++;
    while(!que.empty())
        ans=max(ans,que.front().state),que.pop();
    if(ans)
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

嗯，差不多结束了。反正我不想死磕DP正解

这题的真正的做法是DP，具体做法我就不说了，楼下dalao都是DP。。

DP版code：

#include<bits/stdc++.h>
using namespace std;
int n,beginlev,maxlev;
int f[1001][1001];
int c[1001];
int main()
{
    cin>>n>>beginlev>>maxlev;
    for(int i=1; i<=n; i++)
        cin>>c[i];
    f[0][beginlev]=1;
    for(int i=1; i<=n; i++)
        for(int j=0; j<=maxlev; j++)
        {
            if(f[i-1][j]&&j+c[i]<=maxlev)
                f[i][j+c[i]]=1;
            if(f[i-1][j]&&j-c[i]>=0)
                f[i][j-c[i]]=1;
        }
    for(int i=maxlev; i>=0; i--)
        if(f[n][i])
        {
            cout<<i<<endl;
            return 0;
        }
    cout<<-1<<endl;;
    return 0;
}