ACM-ICPC Asia Beijing Regional Contest 2017-J-Pangu and Stones-구간 dp-합병석자 진급

10438 단어 dpGYM

ACM-ICPC Asia Beijing Regional Contest 2017-J-Pangu and Stones-구간 dp-합병석자 진급


4
  • ACM-ICPC Asia Beijing Regional Contest 2017-J-Pangu and Stones-구간 dp-합병석자 진급
  • Description
  • Input
  • Output
  • Examples
  • Input
  • Output

  • Problem Description
  • Solution
  • Code


  • Description

        In Chinese mythology, Pangu is the first living being and the creator of the sky and
     the earth. He woke up from an egg and split the egg into two parts: the sky and the earth.
    
        At the beginning, there was no mountain on the earth, only stones all over the land.
    
        There were N piles of stones, numbered from 1 to N. Pangu wanted to merge all of them 
    into one pile to build a great mountain. If the sum of stones of some piles was S, Pangu 
    would need S seconds to pile them into one pile, and there would be S stones in the new 
    pile.
    
        Unfortunately, every time Pangu could only merge successive piles into one pile. And 
        the number of piles he merged shouldn't be less than L or greater than R.
    
        Pangu wanted to finish this as soon as possible.
    
        Can you help him? If there was no solution, you should answer '0'.
    

    Input

    
    
        There are multiple test cases.
    
        The first line of each case contains three integers N,L,R as above mentioned 
        (2<=N<=100,2<=L<=R<=N).
    
        The second line of each case contains N integers a1,a2 …aN (1<= ai  <=1000,i= 1…N ),
        indicating the number of stones of  pile 1, pile 2 …pile N.
    
        The number of test cases is less than 110 and there are at most 5 test cases in which N
        >= 50.
    

    Output

    For each test case, you should output the minimum time(in seconds) Pangu had to take . If
    it was impossible for Pangu to do his job, you should output  0.

    Examples


    Input

    3 2 2
    1 2 3
    3 2 3
    1 2 3
    4 3 3
    1 2 3 4

    Output

    9
    6
    0

    Problem Description

           。
          ,       X ,L<=x<=R,                    。       。

    Solution

      dp
        [L,R]dp[L,R]code

    Code

    /*
     * @Author: Simon 
     * @Date: 2018-08-20 13:30:43 
     * @Last Modified by: Simon
     * @Last Modified time: 2018-08-20 14:43:25
     */
    #include
    using namespace std;
    typedef int Int;
    #define int long long
    #define INF 0x3f3f3f3f
    #define maxn 105
    int a[maxn];
    int dp[maxn][maxn][maxn];//dp[i][j][k],   i~j   k        
    Int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n,l,r;
        while(cin>>n>>l>>r)
        {
            memset(dp,INF,sizeof(dp));
            for(int i=1;i<=n;i++)
            {
                dp[i][i][1]=0;
                cin>>a[i];
                a[i]+=a[i-1];
            }
            for(int x=l-1;x//   
            {
                for(int i=1;i+x<=n;i++)
                {
                    int j=x+i;
                    dp[i][j][x+1]=0;// x   ,  x       0
                    dp[i][j][1]=a[j]-a[i-1];//                  
                }
            }
            for(int x=1;x//      
            {
                for(int i=1;i+x<=n;i++)
                {
                    int j=x+i;
                    for(int k=i;kfor(int c=2;c<=x+1;c++)//            
                        {
                            dp[i][j][c]=min(dp[i][j][c],dp[i][k][c-1]+dp[k+1][j][1]);
                        }
                    }
                    for(int c=l;c<=r;c++)//          
                            dp[i][j][1]=min(dp[i][j][1],dp[i][j][c]+a[j]-a[i-1]);
                }
            }
            if(dp[1][n][1]>=INF)
            {
                cout<<0<else cout<1][n][1]<cin.get(),cin.get();
        return 0;
    }

    좋은 웹페이지 즐겨찾기