UVAlive4097 Yungom（思路）-白红宇

UVAlive4097 Yungom（思路）

阅读量：6227 次

发布时间：2019-06-21

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

题意：

给你一个n（200）和d（200），表示你有d种字母，要用他们组成无公共前缀的n个字符串，

接下来给你d个数，以此表示每种字母的花费，问你最小花费

思路：

可以暴力找，首先把d种花费排序，然后存入前d个下标中，如果n>d就后面都存入inf

ans初值为1-n的下标数之和，然后一直用下标为1的那个数当作扩展节点进行扩展，每次扩展d个数，下标为1的节点废除，替换成最后一个节点

然后重新排序，取前n个值更新ans，直到ans比当前的值要小为止即为答案

因为这个过程是先减后增的，一开始前n个数的后几位有可能很大，通过扩充节点可以替换掉他们，使得ans的值减小

然后这个过程会使得前面的数的值增大，当后面的大数替换完成后，肯定会使得前n个数的和一直增大，所以这个过程会有最小值

/* ***********************************************Author        :devil************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define pii pair
                  
                   #define mkp make_pairtemplate
                   
                    inline void rd(T &x){ char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int inf=0x3f3f3f3f;const int mod=1e9+7;const int N=4e2+10;LL a[N];LL b[N];int main(){#ifndef ONLINE_JUDGEIN#endif int n,d; while(~scanf("%d%d",&n,&d)&&n) { LL ans=0; for(int i=1;i<=d;i++) scanf("%lld",&a[i]); sort(a+1,a+1+d); memcpy(b,a,sizeof(a)); for(int i=d+1;i<=n;i++) b[i]=inf; for(int i=1;i<=n;i++) ans+=b[i]; while(1) { for(int i=1;i<=d;i++) b[n+i]=b[1]+a[i]; b[1]=b[n+d]; sort(b+1,b+n+d); LL now=0; for(int i=1;i<=n;i++) now+=b[i]; if(ans>now) ans=now; else break; } printf("%lld\n",ans); } return 0;}

转载于:https://www.cnblogs.com/d-e-v-i-l/p/6079984.html

你可能感兴趣的文章