dp연습 요약

연습경기

T1

무료 파이

어느 날, 왕 학생이 길을 걷고 있는데 갑자기 하늘에서 파이가 크게 떨어졌어요(하하하...).이것은 왕 학우의 인품이 너무 좋다고 말할 수 있을 뿐, 이 파이는 그의 옆의 10미터 범위 내에 떨어졌다.그래서 왕 학생은 바로 파이를 받으러 갔는데, 지방에 떨어진 파이는 먹을 수 없었기 때문이다.그는 이 10미터 범위 내에서만 파이를 받을 수 있다.왕 군은 매우 우수한 Oier이기 때문에 그는 우수한 운동선수가 아니기 때문에 그는 초당 1미터를 넘지 않는 범위 내에서 떨어진 파이를 받을 수 밖에 없다.이제 이 내경에 아이콘 위의 좌표를 지정합니다.
문제를 간소화하기 위해 다음 시간 동안 파이가 0-10이라는 11개 위치에 떨어진다고 가정하자.처음에 왕 군은 5라는 자리에 서 있었기 때문에 1초에 4, 5, 6 세 자리 중 한 자리의 파이만 받았다.왕 군은 파이를 최대 몇 개까지 받을 수 있습니까?(그의 가방이 무궁무진한 파이를 수용할 수 있다고 가정하면) Input 입력 데이터가 얼마나 많은지.각 그룹 데이터의 첫 번째 동작은 양의 정수 n (0) 이다

해석

이 문제를 본 첫인상은 FJ가 애플을 받는 것이었지만 10만 개의 데이터를 보면 반드시 T가 날아갈 것이라는 것을 알았기 때문에 생각을 바꿔야 했다.제목의 뜻에 따르면 왕 군은 한 단위의 시간에 최대 한 칸만 갈 수 있기 때문에 우리는 작은 시간에서 큰 시간까지 일일이 들 수 있다. 그러나 현재 시간의 다음 초 위치는 틀림없이 현재 시간에서 왼쪽으로 가거나 오른쪽으로 가거나 움직이지 않을 것이다.그러니까 밀어줄 수 있어.

코드는 다음과 같다.

#include
using namespace std;
const int dx[3]={0,1,-1};//  ，  ，  
const int MAXN=100050;
int n,maxt,dp[11][MAXN],b[11][MAXN],maxn=-MAXN;
inline int read(){
    int num=0,f=1;
    char c=getchar();
    for(;c>'9'||c<'0';c=getchar())
    if(c=='-')f=-1;
    for(;c>='0'&&c<='9';c=getchar())
    num=(num<<1)+(num<<3)+c-48;
    return num*f;
}
void work(){
    maxn=0;
    dp[5][0]=0;
    b[5][0]=0;//           
    for(int i=0;ifor(int p=0;p<=10;++p)
        if(dp[p][i]>=0){
            for(int k=0;k<=2;++k){
                int newp=p+dx[k];
                if(newp<0||newp>10)continue;//  
                if(b[newp][i+1]<=0)dp[newp][i+1]=max(dp[newp][i+1],dp[p][i]);//       
                else dp[newp][i+1]=max(dp[p][i]+b[newp][i+1],dp[newp][i+1]);//      
                maxn=max(dp[newp][i+1],maxn);
            }
        }
    }
    printf("%d
",maxn);

}
void init(){
    while(1){
        n=read();
        if(n==0)exit(0);
        memset(b,-1,sizeof(b));
        memset(dp,-10,sizeof(dp));
        for(int i=1;i<=n;++i){
            int p=read();
            int ti=read();
            maxt=max(maxt,ti);
            if(b[p][ti]<0)b[p][ti]=0;
            b[p][ti]++;
        }
        work();
    }
}
int main(){
    init();
    return 0;
}

T2

케이크 케이크

한 케이크를 한 번에 한 입 또는 한 번에 k입을 먹을 수 있다면 부피가 x1~x2로 정해지지 않은 케이크는 몇 가지 먹는 방법이 있는지 물어본다.
Input
첫 번째 줄에는 두 개의 정수 t, k(1<=t, k<=100000)가 있는데 그 중에서 t는 데이터의 조수를 나타낸다.다음 t줄, 줄당 두 개수 x1, x2(1<=x1<=x2<=100000).Output은 모두 t줄로 되어 있고 줄마다 정수 x가 있는데 케이크 수량이 x1-x2 사이일 때 모두 몇 가지 다른 먹는 방법이 있음을 나타낸다. 그 결과 (10^9+7)를 본보기로 삼았다.
Sample Input
3 2 1 3 2 3 4 4
Sample Output
6
5
5

해석

이 문제는 매우 까다로워서 계단을 오르기만 하면 반드시 풀 수 있다.주의해야 할 점은 k=1일 때, 한 번에 한 입 먹는 것과 한 번에 한 입 먹는 것은 다르다는 것이다!!!또한 여러 그룹의 데이터가 있기 때문에 시간 초과를 방지하기 위해 가장 큰 x2 방법수를 건네주고 접두사와 조회 구간과 시간은sum[x2]-sum[x1-1]만 있으면 된다.

코드

#include
using namespace std;
const int MAXN=1000000007;
int t,k,x1,x2,dp[100050],ans,maxn,sum[100050];
struct node{
    int l,r;
}e[100050];
inline int read(){
    int num=0,f=1;
    char c=getchar();
    for(;c>'9'||c<'0';c=getchar())
    if(c=='-')f=-1;
    for(;c>='0'&&c<='9';c=getchar())
    num=(num<<1)+(num<<3)+c-48;
    return num*f;
}
void init(){
    t=read();k=read();
    for(int i=1;i<=t;++i){
        e[i].l=read();
        e[i].r=read();
        maxn=max(maxn,e[i].r);
    }
}
void work(){
    dp[0]=1;
    for(int i=1;i<=maxn;++i){
        dp[i]=dp[i-1];
        if(i-k>=0)dp[i]+=dp[i-k];
        dp[i]%=MAXN;
        sum[i]=(sum[i-1]+dp[i])%MAXN;
    }
    for(int i=1;i<=t;++i){
        if(sum[e[i].r]<sum[e[i].l-1])printf("%d
",sum[e[i].r]+MAXN-sum[e[i].l-1]);//%                  MAXN      
        else printf("%d
",sum[e[i].r]-sum[e[i].l-1]);
    }
}
int main(){
    init();
    work();
    return 0;
}

T3

과일.

n개의 과일이 있는데 각 과일마다 두 개의 속성치가 있다. ai는 맛의 정도를 나타내고 비는 에너지치를 나타낸다. 현재 한 개 이상의 과일을 선택해야 한다. 선택한 과일의ai와 비와의 비율은 k가 이런 청형이 나타날 수 있는 상황에서ai의 합이 가장 많으면 얼마냐고 묻는다. 만약에 이런 상황에 출력이 존재하지 않는다면-1
Input
첫 번째 줄은 두 개의 정수 n,k(1 ≤ ≤ 100,  1 ≤ k≤ 10)를 포함한다.두 번째 행위 n개 정수 a1,  a2,  ...,  an(1 ≤ ai ≤ 100) - 과일의 맛값.세 번째 줄은 과일의 에너지치를 포함한다.
Output
하면, 만약, 만약...그렇지 않으면 조건이 충족된ai 누적과
Examples
Input
3 2 10 8 1 2 7 1
Output
18
Input
5 3 4 4 4 4 4 2 2 2 2 2
Output
-1

해석

우선 이 문제는 검색을 사용할 수 없습니다. n=100은 틀림없이 시간을 초과할 것입니다.제목에서 맛있는 것과 가장 큰 것을 요구하는 것을 보고 가방이 생각났다.하지만 직접 배낭을 만들 수는 없으니 바꾸자.제목에 따라suma/sumb=k, 그래서suma=sumb*k, 그래서 가방 용량이suma-sumb*k=0일 때 우리가 요구하는 최대치입니다.또한suma-sumb는 마이너스일 수 있기 때문에suma-sumb를 전체적으로 p로 편이시켜 모두 플러스로 하여 수조로 표시한다.

코드

#include
using namespace std;
const int p=100000;//   
int n,k,dp[150][200000];
struct node{
    int a,b,c;//a    ，b    ，c a-b*k；
}e[150];
inline int read(){
    int num=0,f=1;
    char c=getchar();
    for(;c>'9'||c<'0';c=getchar())
    if(c=='-')f=-1;
    for(;c>='0'&&c<='9';c=getchar())
    num=(num<<1)+(num<<3)+c-48;
    return num*f;
}
void init(){
    n=read();k=read();
    for(int i=1;i<=n;++i)e[i].a=read();
    for(int i=1;i<=n;++i){
        e[i].b=read();
        e[i].c=e[i].a-e[i].b*k;
    }
}
void work(){
    memset(dp,-10,sizeof(dp));
    dp[0][p]=0;
    for(int i=1;i<=n;++i)
        for(int j=p*2;j>=e[i].c;--j){
            dp[i][j]=max(dp[i-1][j-e[i].c]+e[i].a,dp[i-1][j]);
        }
        if(dp[n][p]==0)dp[n][p]=-1;
    printf("%d",dp[n][p]);
}
int main(){
    init();
    work();
    return 0;
}