사탕(동적 기획)

문제설명. 엄마가 B 군에게 N 사탕을 사줬어요!하지만 그녀는 B 군이 직접 먹는 것을 허락하지 않았다.만약에 현재 M 덩어리 설탕이 있다고 가정하면 작은 B는 매번 P 덩어리 설탕을 들 수 있는데 그 중에서 P는 M의 뿌리 아래 M보다 크지 않은 질인수이다.이때 엄마는 B군이 P사탕을 가져간 뒤 다시 사탕 더미에서 P사탕을 가져간다.그리고 작은 B는 이어서 사탕을 꺼낼 수 있다.지금 B군은 설탕을 얼마나 많이 받을 수 있는지 알고 싶어 한다.입력 형식 정수 N 출력 형식 최대 설탕 샘플 입력 15 샘플 출력 6 데이터 규모 및 약속 N <= 100000
한 문제를 동태적으로 기획하거나 추론할 수 있는지 판단하는데 그 중의 한 유형의 특징은 문제의 하위 문제와 유사성이다. 예를 들어 이 문제를 설정하면 사탕의 수가 n이고 내가 x개의 설탕을 받았을 때(x를 합법적인 값으로 설정) 남은 것은 n-x*2개이다. 우리는 이 값을 n으로 설정하면 문제를 발견한 것은 다시 처음으로 돌아간다. 단지 설탕의 수량(문제의 규모)이 줄어들었을 뿐이다.같은:상태:d(i)->내가 i개의 사탕에서 얻을 수 있는 최대 개수 상태 이동 방정식:d(i)=Max{d(i-x*2)+x|x는 루트 아래 M보다 크지 않은 모든 질인수} 다음은 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main
{   
    static int dp[];
    static ArrayList list=new ArrayList<>();
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        double k=Math.sqrt(n);
        int number=2;
        int p=1;
        while(number<=k)
        {
            if(p*ptrue;
            for(int i=0;iget(i)<=p;i++)
            {
                if(number%list.get(i)==0)
                {
                    sign=false;
                    break;
                }
            }
            if(sign)list.add(number);
            number++;
        }//   ，        n    
        //System.out.println(list);
        dp=new int[n+1];//DP
        dp[0]=dp[1]=dp[2]=dp[3]=0;
        dp[4]=2;
        System.out.println(find(n));
    }
    static int find(int x)//    
    {
        if(x<=3)return 0;
        if(dp[x]!=0)return dp[x];
        //if(x%2==0)return dp[x]=x>>1;
        dp[x]=0;
        double k=Math.sqrt(x);//k   
        for(int i=0;iget(i)<=k;i++)
        {
            if(x%list.get(i)==0)//      
                dp[x]=Math.max(dp[x], find(x-list.get(i)*2)+list.get(i));
        }
        return dp[x];
    }
}

그러나 유감스럽게도 이 프로그램은 만점을 받지 못했다. n이 21500위안 정도에 있을 때 창고가 넘쳤기 때문이다...이것은 최초의 코드인데, 기왕 뒤에서 앞으로 안 된다면, 이전과 후행만 사용하고 귀속되는 것을 버려야 한다.수정:

import java.util.ArrayList;
import java.util.Scanner;

public class Main 
{   
    static int dp[];
    static ArrayList list=new ArrayList<>();
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        double k=Math.sqrt(n);
        int number=2;
        int p=1;
        while(number<=k)
        {
            if(p*ptrue;
            for(int i=0;iget(i)<=p;i++)
            {
                if(number%list.get(i)==0)
                {
                    sign=false;
                    break;
                }
            }
            if(sign)list.add(number);
            number++;
        }
        //System.out.println(list);
        dp=new int[n+1];
        dp[0]=dp[1]=dp[2]=dp[3]=0;
        dp[4]=2;
        for(int i=5;i<=n;i++)//     ，         dp[i]
        {
            double t=Math.sqrt(i);
            dp[i]=0;//       0，     if     false
            for(int j=0;jget(j)<=t;j++)
            {
                if(i%list.get(j)==0)
                    dp[i]=Math.max(dp[i], dp[i-list.get(j)*2]+list.get(j));
            }
        }
        System.out.println(dp[n]);
    }

}

이것은 ac 코드입니다