BZOJ 1673 [Usaco2005 Dec]Scales 天平：dfs 启发式搜索 A*搜索

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1673

题意：

　　有n个砝码(n <= 1000)，重量为w[i]。

　　你要从中选择一些砝码，使得这些砝码的总重量最大，但不超过c。

　　w[i]按递增顺序给出，并且保证w[i] >= w[i-1]+w[i-2] (i >= 3)。

题解：

　　dfs。

　　因为w[i] >= w[i-1]+w[i-2]，所以其实n最大只有45左右（类似斐波那契数列）。

　　优化：

　　　　（1）启发式：优先选砝码（不跳过），并且优先选重量大的砝码，尽早更新ans。

　　　　（2）A*搜索：如果当前tot + 剩下砝码的总重（前缀和） < ans，则return。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 1005

 using namespace std;

 int n,c;

 int ans=;

 int w[MAX_N];

 long long sum[MAX_N];

 void dfs(int col,int tot)

 {

     if(tot>c) return;

     ans=max(ans,tot);

     if(col>n) return;

     if(tot+sum[n]-sum[col-]<=ans) return;

     dfs(col+,tot+w[col]);

     dfs(col+,tot);

 }

 void read()

 {

     cin>>n>>c;

     for(int i=n;i>=;i--)

     {

         cin>>w[i];

     }

 }

 void solve()

 {

     sum[]=;

     for(int i=;i<=n;i++)

     {

         sum[i]=sum[i-]+w[i];

     }

     dfs(,);

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

BZOJ 1673 [Usaco2005 Dec]Scales 天平：dfs 启发式搜索 A*搜索

最新文章

热门文章