POJ 1950 Dessert
來源：程序員人生 發布時間：2015-05-22 08:11:11 閱讀次數：2583次
題目鏈接~~
題意 ： 給你 n ( 1 <= n <= 15) 個數（1 . 2 . 3 . 4 ....） 在這些數中間添加 + ，- ,。，使得終究的計算結果為 0 ，如果情況不大于 20 種 ，則輸出全部，否則最多輸出 前20 種，按字典序輸出。
解題思路 ：這題和在廣東區域賽的熱身賽的1題差不多，深搜枚舉所有情況，就是處理點的時候需要注意，同時處理的的情況大于等于 10 的數字應當乘 100 。
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <vector>
#include <cmath>
using namespace std ;
const int MX = 100 + 5 ;
const int INF = 0x3f3f3f3f ;
int n ,ans ;
char s[MX] ;
void dfs(int num ,int sum ,int temp ,int pre ,int di) // sum 已計算的總和
{
if(n == num)
{
if(s[num⑴] != '.')
sum += temp*pre ;
else // 大于等于 10 的時候特殊
{
if(num < 10)
sum += (temp*10 + num)*pre ;
else sum += (temp*100 + num)*pre ;
}
if(sum) return ;
ans++ ;
if(ans > 20) return ;
cout<<1 ;
for(int i = 2 ;i <= n ; ++i)
cout<<" "<<s[i⑴]<<" "<<i ;
cout<<endl ;
return ;
}
int Temp = temp ;
if(s[num⑴] == '.')
{
if(num < 10)
Temp = temp*10 + num ;
else Temp = temp*100 + num ;
}
s[num] = '+' ; // +
dfs(num+1 ,sum + Temp*pre ,num+1 ,1 ,0) ;
s[num] = '-' ; // -
dfs(num+1 ,sum + Temp*pre ,num+1 ,⑴ ,0) ;
s[num] = '.' ; // .
if(!di) // 第1次放點
dfs(num+1 ,sum ,num ,pre ,di+1) ;
else
{
if(num < 10) // 注意 >= 10 是需要乘 100
dfs(num+1 ,sum , temp*10 + num ,pre ,di+1) ;
else dfs(num+1 ,sum ,temp*100 + num ,pre ,di+1) ;
}
}
int main()
{
while(~scanf("%d" ,&n))
{
ans = 0 ;
s[0] = '+' ; //
dfs(1 ,0 ,1 ,1 ,0) ; //主要是點的情況特殊
cout<<ans<<endl ;
}
return 0 ;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
