【NOI 1999】バースデーケーキ

2519 ワード

検索

【NOI 1999】バースデーケーキ
Description
7月17日はMr.Wの誕生日で、ACM-THUはこのために体積NπのM層の誕生日ケーキを作り、各層が円柱である.
下から上に向かってi(1<=i<=M)層目のケーキを半径Ri、高さHiの円柱とする.iの場合、Ri>Ri+1およびHi>Hi+1が要求される.
ケーキにクリームを塗るので、できるだけ経費を節約するために、ケーキの外表面(一番下の層の下底面を除く)の面積Qが最小になることを望んでいます.
Q=Sπ
与えられたNとMをプログラミングして、ケーキの作り方(適切なRiとHiの値)を見つけて、Sを最小にしてください.
(Q以外のデータは全て正の整数)
Input
2行あり、第1の挙動N(N<=10000)は、作製されるケーキの体積がNπであることを示す.第2の挙動M(M<=20)は、ケーキの層数がMであることを示す.
Output
1行のみ、正の整数S(解がなければS=0)である.
Sample Input
100
2
Sample Output
68
Hint
附:円柱式
体積V=πR^2 H
側面積A’=2πRH
底面積A=πR^2
Source
[NOI1999]
数学、検索、枝切り
Solution
この問題の面積については,明らかに最下層の表面積だけが計算を必要とし,他の層は側面積だけを考慮する必要がある.
まず、直接検索が遅いことを考慮して、枝を切ることを考慮して、私は2つの枝を書きました.
実行可能性剪断枝(対体積):現在の体積に次の層の最小体積を加えてもnより大きい場合、このスキームは実行できません.
最適性剪定枝(対面積):1、現在の面積に次の層を加えた最小側面積が記録されたansより大きい場合、このスキームは必ずしも最適ではない.2、余剰体積に対応する次の層の側面積に現在の面積がans以上である場合、このスキームは最適ではない(次の層の半径が現在のrを取れないため、以上である必要がある)
枝を切ったら、次の面積と次の高さを列挙して、再帰的に検索すればいいです.
便宜上,各層の最小体積と最小面積をa,b配列に予め処理した.
Code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 2147483647
#define LL long long
using namespace std;

int n, m, a[30], b[30], ans = INF;

inline void search(int v, int s, int p, int r, int h) {//v-->now V, s-->now S, p-->number, r-->now R, h-->now H
  if (p == 0) {
    if (v == n && s < ans) ans = s;
    return ;
  }
  //possible
  if (v + b[p - 1] > n) return ;
  //better
  if (s + a[p - 1] > ans) return ;
  if (2 * (n - v) / r + s>= ans) return ;
  //search the next level's height
  for (int i = r - 1; i >= p; --i) {//for R
    if (p == m) s = i * i;
    int hh = min(h - 1, (n - v - b[p - 1]) / (i * i));
    for (int j = hh; j >= p; --j) search(v + i * i * j, s + 2 * i * j, p - 1, i, j);//for H
  }
}

int main() {
  freopen("1221.in", "r", stdin);
  freopen("1221.out", "w", stdout);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= 20; ++i) a[i] = a[i - 1] + 2 * i * i, b[i] = b[i - 1] + i * i * i;
  search(0, 0, m, n + 1, n + 1);
  if (ans >= INF) printf("0
");
  else printf("%d
", ans);
  return 0;
}

Summary
答えがないと判断する場合に注意

反転将棋

【C言語】接尾辞式変換(接尾辞→接尾辞)