牛客的两道dfs

题意:给你k类物品,每类物品有a[i]个每个物品都有一个value,每类物品最多选一个,要求有多少种选法使得总value>m(没要求每类物品都必须选)

题解:很明显是一道dfs的题,但是要剪枝优化,假设我们当前所有物品的总vaule>m，那么我们只要算这件物品之后的组合总数就行了(特别注意每类物品可以不选,即num[0]=0,dfs每类物品的个数要从位置0开始而不是1),用一个mul数组来记录每类的方案数.

代码:

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <cmath>

 5 #include <algorithm>

 6 #include <stack>

 7 #include <queue>

 8 #include <vector>

 9 #include <map>

10 #include <set>

11 #include <unordered_set>

12 #include <unordered_map>

13 #define ll long long

14 #define fi first

15 #define se second

16 #define pb push_back

17 #define me memset

18 const int N = 1e6 + 10;

19 const int mod = 1e9 + 7;

20 using namespace std;

21 typedef pair<int,int> PII;

22 typedef pair<long,long> PLL;

23

24 int k;

25 ll m,ans,a[20][200],mul[20],num[200];

26

27

28 void dfs(int pos,ll sum){

29     if(pos>k) return;

30      for(int i=0;i<=num[pos];++i){

31          if(a[pos][i]+sum>m){

32              ans+=(num[pos]-i+1)*mul[pos+1];

33              return;

34          }

35          dfs(pos+1,sum+a[pos][i]);

36      }

37 }

38

39 int main() {

40     ios::sync_with_stdio(false);

41      while(cin>>k>>m){

42          for(int i=1;i<=k;++i){

43              cin>>num[i];

44              for(int j=1;j<=num[i];++j){

45                  cin>>a[i][j];

46              }

47              sort(a[i]+1,a[i]+1+num[i]);

48          }

49          ans=0;

50          mul[k+1]=1;

51          for(int i=k;i>=1;--i) mul[i]=mul[i+1]*(num[i]+1);

52          dfs(1,0);

53         printf("%lld\n",ans);

54      }

55

56     return 0;

57 }

2.传送门:牛客14132-贝伦卡斯泰露

题意:问是否可以将一个数组变成成两个完全相同的数组(元素必须从子序列选)

题解:可以直接暴搜,a[ne]表示的是我当前要添加给a1或a2的值,假如它等于a1，那么就给a2，否则给a1(即a2放不放数永远看a1)，假如a1或a2的长度>n/2，就说明这种方案不行,回溯.因为无论如何第一个数一定给a1，所以直接dfs(1,0,2);

代码:

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <cmath>

 5 #include <algorithm>

 6 #include <stack>

 7 #include <queue>

 8 #include <vector>

 9 #include <map>

10 #include <set>

11 #include <unordered_set>

12 #include <unordered_map>

13 #define ll long long

14 #define fi first

15 #define se second

16 #define pb push_back

17 #define me memset

18 const int N = 1e6 + 10;

19 const int mod = 1e9 + 7;

20 using namespace std;

21 typedef pair<int,int> PII;

22 typedef pair<long,long> PLL;

23

24 int t;

25 int n,a[N];

26 int a1[N],a2[N];

27

28 bool dfs(int p1,int p2,int ne){

29     if(p1>n/2 || p2>n/2) return false;

30     if(ne==n+1) return true;

31     if(a[ne]==a1[p2+1]){

32         a2[p2+1]=a[ne];

33         if(dfs(p1,p2+1,ne+1)) return true;

34     }

35     a1[p1+1]=a[ne];

36     return dfs(p1+1,p2,ne+1);

37 }

38

39 int main() {

40     ios::sync_with_stdio(false);

41     cin>>t;

42      while(t--){

43          cin>>n;

44           for(int i=1;i<=n;++i) cin>>a[i];

45

46           a1[1]=a[1];

47           if(dfs(1,0,2)) printf("Frederica Bernkastel\n");

48           else printf("Furude Rika\n");

49

50      }

51

52     return 0;

53 }

巴特西

牛客的两道dfs

最新文章

热门文章