[HAOI2012] 音量调节

(装做自己很强的样子( o) 实际上弱爆了(color{white}{我想颓废})

开始的时候想了一个很迷惑的错误的(dp)(因为后来发现它就是个错误的贪心

正确的状态是(dp[i][j]=0/1)表示是否可以在第(i)首歌时达到(j)音量。

那么初始状态就是(dp[0][beginLevel]=1)

转移枚举音量

(color{Green}{dp[i-1][j]==1?})(color{SkyBlue}{j+c[i]leq maxLevel?f[i][j+c[i]]=1: ;}color{Gold}{j-c[i]geq 0?f[i][j-c[i]]=1: ;}color{Green}{: ;})

多种色彩应该好李姐一些

#include<bits/stdc++.h>

using namespace std;

int n,st,Max;
int c[55];

int f[55][1010];

int main() {
	scanf("%d%d%d",&n,&st,&Max);
	for(int i=1;i<=n;i++) 
		scanf("%d",&c[i]);
	f[0][st]=1;
	for(int i=1;i<=n;i++) {
		for(int j=Max;j>=0;j--) {
			if(f[i-1][j]==1) {
				if(j+c[i]<=Max)
					f[i][j+c[i]]=1;
				if(j-c[i]>=0)
					f[i][j-c[i]]=1;
			}
		}
	}
	int ans=-1;
	for(int i=1;i<=Max;i++) {
		if(f[n][i])
			ans=max(ans,i);
	}
	printf("%d",ans);
	return 0;
}

(最近博客真的极度水

原文地址:https://www.cnblogs.com/zhuier-xquan/p/12150442.html