T1:【bzoj2748】[HAOI2012]音量调节
Description
一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn，表示在第i首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。
Input
第一行依次为三个整数：n, beginLevel, maxlevel。
第二行依次为n个整数：c1,c2,c3…..cn。
Output
输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于0或者高于maxLevel，输出-1。
Sample Input
3 5 10
5 3 7
Sample Output
10
HINT
1<=N<=50,1<=Ci<=Maxlevel 1<=maxlevel<=1000
0<=beginlevel<=maxlevel
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int n,b,ma;
int v[500];
bool f[505][5000];//第i首歌，音量为i能否出现
inline int read(){
int x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
main(){
n=read();
b=read();
ma=read();
for(register int i=1;i<=n;++i){
v[i]=read();
}
f[0][b]=true;
for(int i=1;i<=n;i++){
for(int j=0;j<=ma;j++){
if(j+v[i]<=ma){
if(f[i-1][j])
f[i][j+v[i]]=1;
}
if(j-v[i]>=0){
if(f[i-1][j])
f[i][j-v[i]]=1;
}
}
}
for(int i=ma;i>0;i--)
if(f[n][i]){
printf("%d",i);
return 0;
}
puts("-1");
return 0;
}
T2：一道与上一道类似的题：
题目描述
【问题描述】
杯具选手wyz喜欢玩杯具。
wyz有2个容量分别为n单位、m单位的没有刻度的杯具。wyz有t分钟可以摆弄他的杯具。每一分钟，他都可以做下面4件事中的任意一件：
(1)用水龙头放满一个杯具。
(2)倒空一个杯具。
(3)把一个杯具里的水倒到另一个杯具里，直到一个杯具空了或者另一个杯具满了。（看哪种情况先发生）
(4)什么都不做。
wyz希望最后能获得d个单位的水，假设最后两个杯具中水量的总和为x，那么他的不开心度就为|d-x|。
现在你想知道，wyz的不开心度最小是多少。
【输入格式】
输入到cups.in
第一行4个整数n、m、t、d，分别表示两个杯具的容量、时间限制以及期望值。
【输出格式】
输出到cups.out
一行一个整数表示wyz的最小不开心度。
【输入输出样例】
cups.in
cups.out
7 25 2 16
9
【数据范围】
对于10%的数据，保证t=1
对于20%的数据，保证t<=2
对于40%的数据，保证t<=4
对于100%的数据，保证1<=n,m<=100，1<=t<=100，1<=d<=200
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define N 105
using namespace std;
int n,m,t,d;
int x;
inline int read(){
int x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int f[N][N][N];
int main(){
n=read();
m=read();
t=read();
d=read();
f[0][0][0]=1;
for(register int i=0;i<=t;i++){
for(register int j=0;j<=n;j++){
for(register int k=0;k<=m;k++){
if(!f[i][j][k]) continue;
f[i+1][j][k]=true;
f[i+1][0][k]=true;
f[i+1][j][0]=true;
f[i+1][n][k]=true;
f[i+1][j][m]=true;
if(n-j>=k)
f[i+1][j+k][0]=true;
else
f[i+1][n][j+k-n]=true;
if(m-k>=j)
f[i+1][0][k+j]=true;
else
f[i+1][k+j-m][m]=true;
}
}
}
int ans=21474830;
for(register int i=0;i<=t;++i){
for(register int j=0;j<=n;++j){
for(register int k=0;k<=m;++k){
if(f[i][j][k])
ans=min(ans,abs(j+k-d));
}
}
}
printf("%d",ans);
return 0;
}
啦啦啦
京公网安备 11010502036488号