NOIP 模拟10.20

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;

}

啦啦啦