題目要求

P2036題目鏈接

分析

這是一個(gè)入坑級(jí)的DFS題

用遞歸完成DFS即可。
下面遞歸代碼的i表示當(dāng)前配料的ID，因?yàn)橐鹨粐L試的嘛。x表示酸度，由于是×，初始1；y表示甜度，由于+，初值0。遞歸的終結(jié)篇一定要讓i>num，保證跑完一趟。
既然要求酸度和甜度的絕對(duì)差最小，那就在i>num，遞歸終止前比較更新一下min的值就好啦。
遞歸的時(shí)候在每次分叉的時(shí)候都要分別進(jìn)行本次選和不選兩種情況的遞歸，每次都分兩種情況，類似搜索樹(shù)，也正印證了本題是樸素的DFS遞歸搜索題（當(dāng)然也可以不用遞歸啦）。這里比較樸素，應(yīng)該是O(2ⁿ)吧，畢竟沒(méi)法去剪枝啥的，你不到最后也不知道結(jié)果是怎樣的呀Orz……
1<=N<=10，2¹⁰=1024，炸不了的，完美……

很惡心的一點(diǎn)是result要賦初值為0x3f3f3f3f，當(dāng)然可以有很多種賦值，如果不管的話會(huì)得到42分，WA到自閉。

看這位大佬的博客，也可提供另一種思路 → 位運(yùn)算解法

AC代碼（Java語(yǔ)言描述）

import java.util.Scanner;public class Main {private static int[] acidity_array;private static int[] sweetness_array;private static int num;private static long result = 0x3f3f3f3f;private static void dfs(int i, long x, long y) {if(i > num){if(x!=1 || y!=0) {result = Math.min(Math.abs(x-y), result);}return;}//添加的情況dfs(i + 1, x * acidity_array[i], y + sweetness_array[i]);//不添加的情況dfs(i + 1, x, y);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);num = scanner.nextInt();acidity_array = new int[num+1];sweetness_array = new int[num+1];for (int i = 1; i <= num; i++) {acidity_array[i] = scanner.nextInt();sweetness_array[i] = scanner.nextInt();}scanner.close();dfs(1, 1, 0);System.out.println(result);}}

總結(jié)

以上是生活随笔為你收集整理的PERKET（洛谷P2036题题解，Java语言描述）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。