大疆编程 第三题 怎么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; }代码不规整的地方,还请轻喷
#大疆##笔试题目#