小Q是篮球训练队的教练,篮球队新加入了N名队员,第i名队员的篮球水平值为ai。
小Q现在要把他们按照以下的要求分为A队和B队进行训练:
1、A队的队员水平值之和严格大于B队的队员水平值之和
2、对于A队中的任意一名队员,如果把他分配到B队,A队的水平值之和就会严格小于B队的水平值之和。
3、每个队员必须要加入一个队伍
小Q现在想知道有多少种方案可以按照以上要求完成分队。
输入包括两行, 输入的第一行为一个正整数n(2 <= N <= 50), 表示队员的数量。
第二行包括N个正整数 ai(1 <= ai <= 6 x 104), 表示每名队员的篮球水平值, 以空格分割。
输出一个正整数, 表示方案数。
4 5 4 7 6
2
'''Python写的 前后困扰了几个月,现在总结下:用一维数组dp方法(因为回溯剪枝实测真的很慢) 根据题意,A堆总重量严格大于B,但移动A堆任意一个苹果到B,A堆总重量严格小于B,说明,A和B的重量差一定小于A里面苹果重量的最小值的2倍 那么我们枚举A里面苹果最小值,假设枚举到w[i],比w[i]小的肯定都在B那里 比w[i]大的就开始01背包,01背包的结果出来之后,统计一下sum(A)-sum(B)小于2 * w[i]有多少种情况 如果我们按照能力值arry从大到小排序,那么枚举过程相当于一次01背包 ''' n = int(input()) array = list(map(int,input().split())) #把能力值按大小逆序排列 array = sorted(array, reverse=True) all_sum = sum(array) result = 0 f = [1] + [0]*all_sum for i in range(n): #因为每个队员只能"用"一次,因此必须从后往前进行,若是完全背包能用无限次,则从前往后 for j in range(all_sum, array[i]-1, -1): #枚举到A队最小为array[i]时,更新A队总能力值能恰好达到j的情况(因一定有j>=arry[i],所以j不必从所有总能力值判断到0,到arry[i]即可) #其中放入array[i]后A队能力值能正好达到j的,放入前的能力值一定是j-array[i] f[j] = f[j] + f[j - array[i]] #判断j-arry[i]中放进arry[i]这种情况是否符合分队的两个要求,符合则结果加上能力值恰为j-arry[i]的所有情况 if j > all_sum-j and j-array[i] < all_sum-j+array[i]: result += f[j-array[i]] print(result)#by 我之渺小
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; long n_sum = 0; for (int i = 0; i < n; i++){ arr[i]=sc.nextInt(); n_sum += arr[i]; } solution(arr,n,n_sum); } private static void solution(int[] arr,int n,long n_sum) { long ans = 0; //降序 Arrays.sort(arr); ArrayList<Integer> list = new ArrayList<>(); for (int i: arr){ list.add(i); } Collections.reverse(list); int[] newArr = new int[arr.length]; for (int i = 0; i < list.size(); i++){ newArr[i]=list.get(i); } long[][] dp = new long[2][(int)n_sum+1]; dp[0][0] = 1;//0个商品,总价值数0的方案数 for (int j = 1; j <= n_sum;j++){ dp[0][j]=0;//0个商品,总价值数为j的方案数量为0 } for (int i = 0; i < n; i++){ for (int j = 1; j < n_sum; j++){ dp[1][j]=dp[0][j];//未加入商品价值 if (j-newArr[i]>=0){ dp[1][j]+=dp[0][j-newArr[i]]; if (j>n_sum-j&&j-newArr[i]<n_sum-j+newArr[i]){ ans += dp[0][j-newArr[i]]; } } } //更新 for (int j = 1; j < n_sum; j++){ dp[0][j] = dp[1][j]; } } System.out.println(ans); } }
//此版本解题思路参照大佬“我之渺小”,该版本为C++版本 #include <iostream> #include <algorithm> using namespace std; void basketball(int* arr, int n) { sort(arr, arr+n, greater<int>()); long long sum = 0; long long result = 0; for(int i=0; i<n; i++) { sum += arr[i]; } int dp[sum+1]; dp[0] = 1; for(long long i=1;i<sum+1;i++) { dp[i]=0; } for(int i=0;i<n;i++) { for(long long j=sum; j>=arr[i];j--) { dp[j] = dp[j-arr[i]] + dp[j]; if ((j > sum-j) && (j-arr[i] < sum-j+arr[i])) { result += dp[j-arr[i]]; } } } cout<<result<<endl; } int main() { int n; cin>>n; int a[n]; for(int i=0; i<n; i++) { cin>>a[i]; } basketball(a, n); return 0; }
/* DFS,剪枝后也超时,考虑动态规划 从大到小排序 dp[i][A_sum]为 对于第i个队员,A队到达总水平值A_sum的方案数,i之后的队员都加入B 当满足条件1,2,3 即 A_sum > n_sum-A_sum 并且 A_sum-a[i] < n_sum-A_sum+a[i] 时, 当前i队员放入A队的方案数应加入到总方案数中 ans += dp[i][A_sum-a[i]] dp[i][A_sum] = dp[i-1][A_sum] + dp[i-1][A_sum-a[i]] (第i个队员加入或不加入A队) by the way: 优化小技巧,1、除以公约数,结果不变,n_sum指数减小 */ #include <bits/stdc++.h> using namespace std; #define N 50 int n, n_sum; int a[N], dp[60000 * N] = {1}; int gcd(int x, int y) { return y ? gcd(y, x % y) : x; } long long solve() { int g = a[0]; for(int i = 1; i < n; ++i) g = gcd(g, a[i]); for(int i = 0; i < n; ++i) { a[i] /= g; n_sum += a[i]; } sort(a, a + n, greater<int>()); long long ans = 0, i, A_sum; for(int i = 0; i < n; ++i) { for(int A_sum = n_sum; A_sum >= a[i]; --A_sum) { if(dp[A_sum - a[i]]>0 && A_sum > n_sum - A_sum && A_sum - a[i] < n_sum - A_sum + a[i]) { ans += dp[A_sum - a[i]]; } dp[A_sum] += dp[A_sum - a[i]] ; } } return ans; } int main(void) { // freopen("input.txt", "r", stdin); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", a + i); } long long ans = solve(); printf("%lld", ans); return 0; }
//转化为0-1背包问题 设目前有A包,共n个商品,依次决定是否放入商品i,使商品总价值 //达到指定数目(未放入的,则默认加入B包) //定义数组dp,其中dp[i][j]表示前i个商品中,使A包总价值为j的放置方案数量 //dp[i][j]=dp[i-1][j]+dp[i-1][j-arr[i]]; (不放入商品i,和放入商品i的情况。 //加号后一项需满足条件j-arr[i]>=0) //本问题的特殊性 //在计算dp前,对价值数组arr进行降序(降序是为方便计算条件2中A包的商品最小价值); //条件2表示 取A包内最小价值的商品放入B包,新A包总价值 < 新B包总价值 //数组dp中,dp[i][j]表示前i个商品中,使A包总价值为j的放置方案数量。此时, //如商品i放入A包,则A包内的商品最小价值为arr[i](降序)。 //若满足j>n_sum==j && j-arr[i]<n-j-arr[i],表示当前放置方案满足1,2,3条件, //(A包总价值j,i往后的商品都放入B包,B包总价值n_sum-j,且A包内商品最小价值arr[i]) //则 ans+=dp[i-1][j-arr[i]](ans记录满足条件1,2,3的方案总数) // 如定义dp[n][n_sum+1],则通过率60%,内存超限。因此定义dp[2][n_sum+1],因为每次 //计算一行仅仅利用了上面一行的元素值。 #include<iostream> #include<algorithm> using namespace std; void arrange(int*arr, int n){ sort(arr, arr+n, greater<int>()); //降序 long long n_sum=0, ans=0; for(int i=0; i<n; i++) n_sum += arr[i]; int dp[2][n_sum+1]; // dp[0]表示在arr[i]之前的商品,放置方案数量,dp[1]表示加入商品arr[i]后,方案数量 dp[0][0]=1; // 0个商品,总价值数为0的方案数量为1 for(int j=1;j<=n_sum;dp[0][j]=0,j++); // 0个商品,总价值数为j(j>=1)的方案数量为0 for(int i=0; i<n; i++){ for(int j=1;j<n_sum; j++){ dp[1][j] = dp[0][j]; // 未加入商品价值arr[i] if(j-arr[i]>=0){ dp[1][j] += dp[0][j-arr[i]]; // 加入商品价值arr[i] if (j>n_sum-j && j-arr[i]<n_sum-j+arr[i]) ans+=dp[0][j-arr[i]]; //满足条件1,2,3,则修改计数ans } } for(int j=1; j<n_sum; dp[0][j]=dp[1][j], j++);//更新dp[0] } cout<<ans<<endl; } int main(){ int n; cin>>n; int arr[n]; for(int i=0; i<n; i++) cin>>arr[i]; arrange(arr, n); return 0; }
根据顶部“我之渺小”大佬的代码改的java版本,需要注意的就是整数类型防止越界
import java.util.Scanner; import java.util.Arrays; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; long total_sum = 0; for(int i = 0; i < n; i++){ arr[i] = sc.nextInt(); total_sum += arr[i]; } Arrays.sort(arr); long[] dp = new long[(int)total_sum + 1]; dp[0] = 1; long ans = 0; for(int i = n - 1; i >= 0; i--){ for(int j = (int) total_sum; j >= arr[i]; j--){ // 利用滚动数组从后向前更新就可以只用一维数组 dp[j] += dp[(int)(j - arr[i])]; if(j > total_sum - j && j - arr[i] < total_sum - j + arr[i]){ ans += dp[(int)(j - arr[i])]; } } } System.out.println(ans); } }
#include <bits/stdc++.h> #define LL long long using namespace std; const int AX = 3e6 + 666 ; int a[AX] ; int n , S ; LL res ; LL dp[AX] ; int main(){ cin >> n ; S = 0 ; res = 0 ; for( int i = 0 ; i < n ; i++ ){ cin >> a[i] ; S += a[i] ; } memset( dp , 0LL , sizeof(dp) ) ; sort( a , a + n ) ; dp[0] = 1 ; for( int i = n - 1 ; i >= 0 ; i-- ){ //Sa_min /*从大到小枚举Sa最小值,因为每次都要保证小于a[i]的Sa值的方案数dp[Sa]=0 (因为a[i]是目前Sa的最小值,小于其的Sa方案数只能为0)*/ for( int j = S ; j >= a[i] ; j-- ){ // 0-1:装满Sa方案数 dp[j] += dp[j-a[i]] ; int Sb = S - j ; /*若满足Sa>Sb && Sa-a[i]<Sb+a[i],方案++*/ if( j > Sb && j - a[i] < Sb + a[i] ) res += dp[j-a[i]] ; } } cout << res << endl; return 0 ; }
#include <bits/stdc++.h> using namespace std; bool cmp(long a, long b){ return a>b; } int main(){ int n; cin>>n; long a[n],s=0,cnt=0; for(int i=0;i<n;i++){ cin>>a[i]; s += a[i]; } sort(a,a+n,cmp); long dp[s+1]; memset(dp,0,sizeof(dp)); dp[0] = 1; for(int i=0;i<n;i++) for(int j=s;j>=a[i];j--){ dp[j] += dp[j-a[i]]; if((2*j>s) && (2*(j-a[i])<s)) cnt += dp[j-a[i]]; } cout<<cnt<<endl; return 0; }
package main import ( "fmt" "sort" ) func main() { var n int fmt.Scan(&n) a := make([]int, n) sum := 0 for i:=0; i<n; i++ { fmt.Scan(&a[i]) sum += a[i] } // 能力值倒序排列 sort.Sort(sort.IntSlice(a)) sort.Sort(sort.Reverse(sort.IntSlice(a))) res := 0 // 01背包 dp := make([]int, sum + 1) dp[0] = 1 for i:=1; i<=sum; i++ { dp[i] = 0 } for i:=0; i<n; i++ { for j:=sum; j>=a[i]; j-- { dp[j] = dp[j] + dp[j - a[i]] if (j > sum - j) && (j - a[i] < sum - j + a[i]) { res += dp[j - a[i]] } } } fmt.Println(res) }
/*讲一下思路吧,本质上还是背包问题 有2个问题需要考虑 一. 怎么保证A队的水平值之和严格大于B队? 假设所有队员的水平值总和为sum, A队的水平值之和为a 显然只需要满足 a > (sum - a) 即可 二. 怎么保证在一的条件下,将A中任一队员替换到B队后,A队的水平值之和严格小于B队? 假设水平值总和为sum, A队的水平值和为a 等价于对A队的任一队员, 不妨设他的水平值为x 都满足 a-x < (sum-a)+x ==> 2a - sum < 2x 因为sum和a都是定值, 显然当x取最小值时, 该式子对任意的x恒成立 知道问题的关键在于最小值后,我们可以枚举在A队的队员水平值最低为x的情况下, 满足上述条件的方案有多少,最后累加起来即可 定义 dp[i][j] 代表前i个队员中可以组成水平值和为j的方案数目 简单的01背包 转移方程就是dp[i][j] = dp[i-1][j] + dp[i-1][j-p[i]] 然后我们将队员的水平值按从大到小排序 假设当前枚举的索引为i,即方案的最小值为p[i] (p数组存储的队员水平值, i >= 1) 为了满足条件一 : j的最小值为(sum+1)/2+(sum&1 ? 0 : 1) (j代表枚举的水平值和) 为了满足条件二 : j的最大值为(sum+2*p[i])/2 + ((sum+2*p[i])&1 ? 0 : -1) 然后从小到大将可行的方案累加起来 这里有一个小问题是,j不能取得过大。 按照题目所给的条件,j最大可以为3000000,这会直接导致memory超限 不过实际上没有必要取这么大,经过不断的测试发现,j取851479为最佳 */#include<stdio.h> #include<vector> #include<algorithm> using namespace std; using ll = long long; static constexpr ll M = 851479; int main() { int n; while (~scanf("%d", &n)) { int p[n]; ll sum = 0; for (int i = 0; i < n; ++i) scanf("%d", &p[i]), sum += p[i]; sort(p, p+n, [](int a, int b){ return a > b; }); int dp[n+1][M+1]; for (int i = 0; i <= M; ++i) dp[0][i] = 0; dp[0][0] = 1; for (int i = 1; i <= n; ++i) for (int j = 0; j <= M; ++j) { dp[i][j] = dp[i-1][j]; if (j >= p[i-1]) dp[i][j] += dp[i-1][j-p[i-1]]; } ll res = 0; for (int i = 1; i <= n; ++i) { ll l = (sum+1)/2 + (sum&1 ? 0 : 1); ll r = (sum+2*p[i-1])/2 + ((sum+2*p[i-1])&1 ? 0 : -1); r = min(r, M); for (ll j = l; j <= r; ++j) if (j-p[i-1] >= 0) res += dp[i-1][j-p[i-1]]; } printf("%lld\n", res); } }
//参照前面的各位大佬 加了更易懂的解释 //01背包问题 import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int len = in.nextInt(); int[] arr = new int[len]; long sum = 0; for (int i = 0; i < len; i++){ arr[i] = in.nextInt(); sum += arr[i]; } Arrays.sort(arr); long ans = 0; long[] dp = new long[(int)sum + 1]; // 分配初始值 dp[0] = 1; for (int i = len - 1; i >= 0; i--){ // j代表B队的当前总价值,j - arr[i]代表A队总价值 for (int j = (int)sum; j >= arr[i]; j--){ // 加上i的总价值 dp[j] += dp[j - arr[i]]; // 如果交换后B > A(j > sum - j) 交换前A > B(sum - (j - arr[i]) > j - arr[i]), if (j > sum - j && sum - (j - arr[i]) > j - arr[i]){ ans += dp[j - arr[i]]; } } } System.out.println(ans); } }
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();//队员的数量 List<Long> levelsList = new ArrayList<>();//队员的水平值 long sumLevel = 0;//总的水平值 for (int i = 0; i < n; i++) { long level = sc.nextLong(); levelsList.add(level); sumLevel += level; } levelsList.sort((a, b) -> (int) (b - a));//降序排列 long[] levels = levelsList.stream().mapToLong(Long::valueOf).toArray(); long[][] dp = new long[2][(int) sumLevel + 1]; dp[0][0] = 1;//初始化 dp 数组 : 0 个队员,水平值为 0 long plans = 0;//可选的方案数 for (int i = 0; i < n; i++) {//队员(商品)[水平值已降序] for (int j = 1; j < sumLevel; j++) {//水平值(背包内物品总重量) dp[1][j] = dp[0][j];//尚未加入队员 i 的水平值 if (j - levels[i] >= 0) { if (j > sumLevel - j && j - levels[i] < sumLevel - j + levels[i]) { plans += dp[0][(int) (j - levels[i])]; } dp[1][j] += dp[0][(int) (j - levels[i])];//加入队员 i 的水平值 } } for (int j = 1; j < sumLevel; j++) { dp[0][j] = dp[1][j]; } } System.out.println(plans); } }
#include <bits/stdc++.h> using namespace std; const int maxn = 4e6 + 10; typedef long long ll; ll dp[maxn],sum = 0; ll a[maxn]; bool cmp(int a,int b){return a > b;} int main() { int n;scanf("%d",&n); for(int i = 1; i <= n; i++) scanf("%lld",&a[i]),sum += a[i]; sort(a + 1,a + 1 + n,cmp); dp[0] = 1; ll ans = 0; for(int i = 1; i <= n; i++) { for(int j = sum; j >= a[i]; j--) { dp[j] += dp[j - a[i]]; if(j > sum - j && j - a[i] < sum - j + a[i]) ans += dp[j - a[i]]; // 这个方案考虑近答案 } } cout<<ans<<endl; return 0; }
#include <iostream> #include <vector> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; static int allcount = 0; void backtrack(vector<int>arr, vector<int> A, vector<int> B, int index) { if (index == arr.size()) { int sumA = 0; int sumB = 0; for (int i = 0; i < A.size(); ++i) { sumA += A[i]; } for (int j = 0; j < B.size(); ++j) { sumB += B[j]; } if (sumA > sumB)//A严格大于B { for (int i = 0; i < A.size(); ++i) { if (sumA - A[i] >= sumB + A[i]) return; } allcount++; /* cout << "ARR" << endl; for (auto s : A) { cout << s << " "; } cout << endl; for (auto s : B) { cout << s << " "; } cout << endl;*/ } return; } A.push_back(arr[index]); backtrack(arr, A, B, ++index); A.pop_back(); index--; B.push_back(arr[index]); backtrack(arr, A, B, ++index); B.pop_back(); } int main() { int n; vector<int> arr; cin >> n; int num; while (n--) { cin >> num; arr.push_back(num); } vector<int>A, B; backtrack(arr, A, B, 0); cout << allcount << endl; // system("pause"); return 0; }只通过30%。
#coding:utf-8 n = int(input()) arrs = list( map(int,input().split())) arrs = sorted(arrs,reverse=True) all_sum = sum(arrs) res = 0 dp = [[0 for i in range(all_sum+1)] for i in range(2)] for i in range(all_sum+1): dp[0][i] = 0 dp[0][0] = 1 for i in range(0,n): for j in range(1,all_sum+1): dp[1][j] = dp[0][j] if arrs[i] <= j: dp[1][j] = dp[1][j] + dp[0][j-arrs[i]] if j>all_sum-j and j-arrs[i]<all_sum-j+arrs[i]: res = res + dp[0][j-arrs[i]] for j in range(1,all_sum): dp[0][j] = dp[1][j] print(str(res))用python照着通过的C++打的,居然只通过50%,时间差这么大吗?
// ConsoleApplication10.cpp : 定义控制台应用程序的入口点。