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

#大疆##笔试题目#
全部评论
system.out.println(1);也是ac百分之50
点赞 回复 分享
发布于 2019-08-06 21:54
原因可能是取余有问题。res,应该是long型。
点赞 回复 分享
发布于 2019-08-06 21:53
我也是贪心加回溯,过了50,反正很迷
点赞 回复 分享
发布于 2019-08-06 21:39
我也是50%,最后改的时候尝试每次都取余也没用
点赞 回复 分享
发布于 2019-08-06 21:27
大佬问下,为啥要对10000007取余
点赞 回复 分享
发布于 2019-08-06 21:20

相关推荐

群星之怒:不是哥们,你就不好奇瘫痪三十年的老植物人是啥样的吗?
点赞 评论 收藏
分享
评论
点赞
4
分享

创作者周榜

更多
牛客网
牛客企业服务