P1877
HighPerformanceRobot
2018-11-30 22:01:01
## 音量调节
作为蒟蒻的我，一开始看到这题想的都是什么搜索，结果暴力打上去一看TLE四个点。。然后~~我作弊加了#pragma GCC optimize（3），最后MLE四个点，而且还是原来那四个TLE的点。~~啊啊啊，BFS都不能过，你们让不让人活？
好吧，暴力BFS的60分做法程序：
```cpp
#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：
```cpp
#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：
```cpp
#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;
}
```