【bzoj2748】音量调节

  • 本文为博主原创，未经许可不得转载

刷水题的感觉真爽

很普通的dp，随手秒掉

用$f[i][j]$表示前i首曲子能否达到音量j，然后。。。随便转移了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
int n,m,a[55],f[55][1010];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  f[0][read()]=1;  m=read();
	for(int i=1;i<=n;++i)  a[i]=read();
	for(int i=1;i<=n;++i)
		for(int j=0;j<=m;++j){
			if(j-a[i]>=0&&f[i-1][j-a[i]])  f[i][j]=1;
			if(j+a[i]<=m&&f[i-1][j+a[i]])  f[i][j]=1;
		}
	for(int i=m;i;--i) if(f[n][i]) {printf("%d\n",i);  return 0;}
	printf("-1\n"); 
	return 0;
}

本文标题:【bzoj2748】音量调节

文章作者:chty

发布时间:2017年03月12日 - 21时46分

最后更新:2018年03月02日 - 17时25分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,