Luogu P1880 [NOI1995]石子合并-白红宇

Luogu P1880 [NOI1995]石子合并

阅读量：5259 次

发布时间：2019-06-14

本文共 867 字，大约阅读时间需要 2 分钟。

题意：

　　在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分

　　求最大值和最小值

思路：

　　因为最后一步是把两个石子和成一个，这时环形和线形是等价的，所以每一种环形的合成方式都可以找到一种等价的线形方式

　　就可以把环形的合并石子拆成分别以i（0<=i<n）为起点的线状合并石子，就max就行了

代码：

#include
     
      #include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #define INF 0x7f7f7f7f#define MAX_INT 0x7fffffff#define pi 3.1415926typedef unsigned int uint;using namespace std;typedef long long LL; int num[205];int dpx[205][105];//dpx[i][j]从i开始的到后j个数的maxint dpn[205][105];int sto[205][105];int main(){ memset(dpx,0,sizeof(dpx)); memset(dpn,0x3f,sizeof(dpn)); int n; cin>>n; for(int i=0;i
             
              >num[i]; num[i+n]=num[i]; dpn[i][0]=dpn[i+n][0]=0; sto[i][0]=sto[i+n][0]=num[i]; } for(int j=1;j

转载于:https://www.cnblogs.com/Gsimt/p/10065874.html

你可能感兴趣的文章