音量调节 bzoj-2748 HAOI-2012
题目大意: 有一个初值, 给你 n 个 $\delta$ 值, 求最后不超过给定的限制的情况下的改变的最大值. 每个 $\delta$ 值可以 + 也可以 -.
注释:$1\le n\le 50$,$1\le 限制 \ le 1000$.
想法: 正负背包. 在背包的之后更新用两行更新, 保证每一个 $\delta$ 值都被计入了答案.
最后, 附上丑陋的代码... ...
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- int c[1001];
- bool v[51][1001];
- int main()
- {
- int n,beginsound,maxsound;
- scanf("%d%d%d",&n,&beginsound,&maxsound);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&c[i]);
- }
- v[0][beginsound]=1;
- for(int i=1;i<=n;i++)
- for(int j=0;j<=maxsound;j++)
- {
- if(j+c[i]<=maxsound)
- {
- if(v[i-1][j+c[i]])
- v[i][j]=1;
- }
- if(j-c[i]>=0)
- {
- if(v[i-1][j-c[i]])
- v[i][j]=1;
- }
- }
- for(int i=maxsound;i>=0;i--)
- {
- if(v[n][i])
- {
- printf("%d",i);
- return 0;
- }
- }
- printf("-1");
- return 0;
- }
小结: 我们通常解题不过是将未知转化成已知, 或者探索未知而已. 而这道题包括大部分的题都是前者.
[bzoj2748][HAOI2012] 音量调节_动态规划_背包 dp
来源: http://www.bubuko.com/infodetail-2666685.html