NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 D. 道具整理

作者 主題: NPSC 2005 高中組 決賽 D. 道具整理  (閱讀 1269 次)

b821213

  • 初級會員
  • **
  • 文章數: 21
    • 檢視個人資料
NPSC 2005 高中組 決賽 D. 道具整理
« 於: 十一月 13, 2011, 08:39:31 pm »

基本上就是把每個物品分開算的暴力搜尋,我寫得不是很好,因此作法僅供參考。

首先如果我們直接枚舉每次把哪兩個合在一起

那麼複雜度是 O((n^2)*n!),其中n最大到10,顯然有點卡。

可行性剪枝很基本,這裡就不提了。

優化1.

我們觀察一下問題,發現重點是決定哪些物品欄最後應該合在一起成為一群。

而同一群中的物品符合交換律,可以亂合一通,所以我們總是枚舉當前第一個物品要跟誰結合,如此一來複雜度就降到了n*(n!)

優化2.

在觀察一下問題,我們發現除非兩個加起來剛好是該物品的最大容量,否則已經處理好的格子每次只會+1,而前述狀況會+2。所以說當現在的情況中能找到兩個合起來剛剛好的,那就一定要這樣做比較好。可是如果序列沒有序,這個檢查的動作就要n^2,因此我們必須維護整個序列是有序的,複雜度跟優化1情形一樣。

優化3.

嚴格說起來這也不算優化......就是優化1其實是有瑕疵的。一種特殊情況下優化1會丟失解,就是第一項物品再也不需要跟別人合了,這意味著格子1的物品數量必須剛好是剩下的渣渣。這種情況下視為把格子1丟掉照樣求解。注意要記錄丟過渣渣了沒,不然可能會丟兩次三次造成wa。

優化4經實驗似乎沒什麼效果,就是先把小的跟大的合在一起,實驗結果顯示無差別......

底下附代碼提供debug


#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

char s[10][20]={
   "RedWater","OrangeWater","BlueWater","WhiteWater",
   "Arrow","Bolt","BrozenArrow","BrozenBolt","IronArrow","IronBolt"
};

int tellme(char* p){
   for(int i=0;i<10;++i)
      if( !strcmp(p,s) ) return i;
   return -1;
}

int item[10][10];
int is[10];
int now[10];
int best;
int m;
int sp;
bool sped = 0;

void dfs(int lv,int nown){
   
   if( lv + nown/2 >= best ) return;
   if( nown <= 1 ){
      if( lv < best ) best = lv;
      return;
   }
   
   for(int i=0,j=nown-1;i<j;++i){
      while( now+now[j] > m && i<j ) --j;
      if( i!=j && now+now[j] == m ){
         --nown ,swap(now[j],now[nown]);
         --nown ,swap(now,now[nown]);
         dfs(lv+1,nown);
         swap(now,now[nown]),++nown;
         swap(now[j],now[nown]),   ++nown;
         return;
      }
   }
   
   
   if( now[0]==sp && !sped ){
      for(int i=0;i<nown-1;++i)
         now = now[i+1];
      sped = 1;
      dfs(lv,nown-1);
      sped = 0;
      for(int i=nown-1;i>0;--i)
         now = now[i-1];
      now[0] = sp;
      return;
   }
      
   int ori = now[0];
   
   for(int i=nown-1;i>0;--i){
      
      if( i<nown-1 && now == now[i+1] ) continue;
      int hold = now;

      if( now[0]+now > m ){ //now[0]搬到now還有剩,但一定比原本的少,序列依舊有序
         
         now[0] -= m-now;
         
         for(int j=i;j<nown-1;++j)
            now[j] = now[j+1];   
               
         dfs(lv+1,nown-1);
         
         for(int j=nown-1;j>i;--j)
            now[j] = now[j-1];
         
         now = hold ,now[0] = ori;
      }
      
      else {               //now[0]+now < m         
         
         now[0] += now , now = 0;
         
         for(int j=i;j<nown-1;++j)
            now[j] = now[j+1];   
         
         int ns = 0;
         while( ns < nown-2 ){
            if( now[ns] <= now[ns+1] ) break;
            else swap(now[ns],now[ns+1]),++ns;
         }
         
         dfs(lv+1,nown-1);
         
         for(int j=ns;j>0;--j)
            now[j] = now[j-1];
         
         
         for(int j=nown-1;j>i;--j)
            now[j] = now[j-1];
         
         now[0] = ori,now = hold;
      }
   }   
}

int main(){
   
   int T;
   scanf("%d",&T);
   
   while(T--){
      
      memset(is,0,sizeof(is));
      
      int k,w;
      char in[100];
      
      scanf("%d",&k);
      
      for(int i=0;i<k;++i){
         scanf("%s %d",in,&w);
         int tmp = tellme(in);
         if( tmp<4 && w==100 ) continue;
         if( tmp>=4 && w==1000 ) continue;
         item[tmp][is[tmp]++] = w;
      }
      
      int ans = 0;
      
      for(int i=0;i<10;++i){   
         int size = is;
         if( size <= 1 ) continue;
         
         for(int j=0;j<size;++j)
            now[j] = item[j];
         
         sort(now,now+size);
         
         m = ( i<4 ) ? 100 : 1000;
         
         int sum = 0;
         for(int j=0;j<size;++j)
            sum+=now[j];
         sp = sum%m;
         
         best = 200000;         
         dfs(0,size);
         ans += best;
      }
      
      printf("%d\n",ans);
   
   }
   
   return 0;   
}

記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 D. 道具整理