题解 P2415 【集合求和】

maozi · 2017-11-11 00:29:43 · 题解

由于楼下大佬们都没有用搜索

因此我就用了个搜索， 模拟的情况都正确 但还是tle了两组数据

不过我觉得 这里应该有一个dfs的题解，

题的大概过程就是枚举每一个位置的元素 对该元素 或者该元素加后面元素的每种状态进行一个累计 这就实现了 集合之和的目的。大概过程就是这样 但是还是tle 搜索还是不很会用啊。

#include<iostream>
#include<string.h>
#include<string>
using namespace std;
int a[35];
bool vis[35];
int sum,t,e;
int z=0;
void dfs(int x){
    int i;
    for(i=x;i<z;i++){    
        sum+=a[i];
        t++;  //t表示在哪一层  第一层的dfs 都是1 向下会一直加 
        e+=sum;//加上这一次计算出来的值 
        dfs(i+1);//cout<<a[i]<<" "<<sum<<" "<<t<<endl;//观察t的回溯 因此可以得到  可以利用t的大小做一个 数组 输出当前层的元素 
        sum-=a[i]; //回溯 
        t--;// 回溯 
    }
}
int main(){
    while(cin>>a[z++]);     z--; //ctrl+z +回车 可查看输出情况 
    memset(vis,0,sizeof(vis));
    dfs(0);
    cout<<e<<endl;
    return 0;
}