【BZOJ2748】【HAOI2012】音量调节

LCF：看到数据范围瞬间会做

// <2748.cpp> - Wed Aug 24 17:05:06 2016
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=1010;
const int INF=1e9;
bool ex[2][MAXN];
int main(){
    int n=gi(),ans=gi(),m=gi(),p=0;
    ex[0][ans]=1;
    while(n--){
        int a=gi();p^=1;
        for(int i=0;i<=m;i++)ex[p][i]=0;
        for(int i=0;i<=m;i++){
            if(!ex[p^1][i])continue;
            if(i-a>=0)ex[p][i-a]=1;
            if(i+a<=m)ex[p][i+a]=1;
        }
    }
    for(int i=m;i>=0;i--)if(ex[p][i]){printf("%d",i);return 0;}
    printf("%d",-1);
    return 0;
}

// <2748.cpp> - Wed Aug 24 17:05:06 2016

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=1010;

const int INF=1e9;

bool ex[2][MAXN];

int main(){

int n=gi(),ans=gi(),m=gi(),p=0;

ex[0][ans]=1;

while(n--){

int a=gi();p^=1;

for(int i=0;i<=m;i++)ex[p][i]=0;

for(int i=0;i<=m;i++){

if(!ex[p^1][i])continue;

if(i-a>=0)ex[p][i-a]=1;

if(i+a<=m)ex[p][i+a]=1;

}

for(int i=m;i>=0;i--)if(ex[p][i]){printf("%d",i);return 0;}

printf("%d",-1);

return 0;

}