大疆编程 第三题 怎么AC
贪心+回溯的思想过了50% 有没有好心人帮忙瞅一瞅
#大疆##笔试题目#
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
void backTracking(vector<int>& cc, vector<int>& index, vector<int>& indexElse, int& res, int num, int value, int target, int i, int M){
if(value == target){
res += 1;
return ;
}
if(value > target || i>=cc.size() || num<=0)
return;
for(int j=num; j>0; j--){
int temp(0);
if(i<index.size()){
value += j*cc[index[i]-1];
backTracking(cc, index, indexElse, res, j-1, value, target, i+1, M);
value -= j*cc[index[i]-1];
}
else{
value += j*cc[indexElse[i-index.size()]-1];
backTracking(cc, index, indexElse, res, j, value, target, i+1, M);
value -= j*cc[indexElse[i-index.size()]-1];
}
}
return ;
}
int main()
{
int V, N;
while (scanf("%d %d", &V, &N) != EOF) {
vector<int> cc(N, 0);
for (int i = 0; i < N; ++i){
int c_i;
cin >> c_i;
cc[i] = c_i;
}
int M;
scanf("%d", &M);
vector<int> index(M, -1);
unordered_map<int, bool> hash;
for (int i = 0; i < M; ++i){
int temp;
scanf("%d", &temp);
index[i] = temp;
hash[index[i]] = true;
}
vector<int> indexElse(N-M, -1);
int index0(0);
for (int i = 0; i < N; ++i){
if(hash[i+1])
continue;
else
indexElse[index0++] = i+1;
}
int res(0), value(0);
backTracking(cc, index, indexElse, res, V/cc[index[0]-1], value, V, 0, M);
printf("%d\n", res% 10000007);
}
return 0;
} 代码不规整的地方,还请轻喷#大疆##笔试题目#

