- 描述
- One day,Tom’s girlfriend give him an array A which contains N integers and asked him:Can you choose some integers from the N integers and the sum of them is equal to K.
- 输入
- There are multiple test cases.
Each test case contains three lines.The first line is an integer
N(1≤N≤20),represents the array contains N integers. The second line
contains N integers,the ith integer represents A[i](-10^8≤A[i]≤10^8).The
third line contains an integer K(-10^8≤K≤10^8). - 输出
- If Tom can choose some integers from the array and their them is K,printf ”Of course,I can!”; other printf ”Sorry,I can’t!”.
- 样例输入
-
4
1 2 4 7
13
4
1 2 4 7
15 - 样例输出
-
Of course,I can!
Sorry,I can't!
题目大意就是，给你n个数， 再给一个sum，能不能用这n个数，加起来等于sum！
主要难点在减少循环。
//时间超限代码：
//Asimple
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define CLS(a) memset(a,0,sizeof (a))
const int maxn = 25;
int n, T, num, cnt, point, line, x, y;
int vis[maxn];//标记数组，标记是否走过
int a[maxn];
bool flag; bool check()
{
for(int i=0; i<n; i++)
if( !vis[i] )
return false ;
return true;
} void DFS(int cnt)
{
if( check() ) return ;
if( cnt == num )
{
flag = true ;
return ;
}
for(int i=0; i<n; i++)
{
if( !vis[i] && cnt + a[i] <= num )
{
vis[i] = 1 ;
DFS(cnt + a[i] ) ;
vis[i] = 0 ;
}
}
} int main()
{
while( cin >> n )
{
cnt = 0 ;
CLS(vis);
flag = false ;
for(int i=0; i<n; i++)
cin >> a[i] ;
cin >> num ;
DFS(cnt);
if( flag ) cout << "Of course,I can!" << endl ;
else cout << "Sorry,I can't!" << endl ;
} return 0;
}减少循环后的代码：
//Asimple
#include <iostream>
using namespace std;
const int maxn = 25;
int n, num, cnt;
int a[maxn];
bool flag; void DFS(int x)
{
if( cnt > num ) return ;
if( cnt == num )
{
flag = true ;
return ;
}
for(int i=x; i<n; i++)
{
cnt += a[i] ;
DFS(i+1);
cnt -= a[i] ;
}
} int main()
{
while( cin >> n )
{
cnt = 0 ;
flag = false ;
for(int i=0; i<n; i++)
cin >> a[i] ;
cin >> num ;
DFS(0);
if( flag ) cout << "Of course,I can!" << endl ;
else cout << "Sorry,I can't!" << endl ;
} return 0;
}