题目

数轴上有M个点a1、a2、…am,另有一个数列p1、p2、…pn,(1 ≤ pii ≤ M)。

给定d1、d2、…dn,对所有的 i (1 ≤ i ≤ n),已知 |api+1 - api| = di,求M得最少可能值。(1 ≤ n ≤ 25 ,1 ≤ ai ≤ 105)

原题链接：http://codeforces.com/group/gRkn7bDfsN/contest/212299/problem/B

思路

基本思路：枚举 api+1 在 api 的左边或右边，为了降低复杂度，强制第一次选向右(向左也可以)。

思路一：利用二进制+位运算，枚举所有的可能

O(2N-1N)

#include
#include
#include
#include
using namespace std;

const int SIZE = ( * ) * + ; //数轴的范围
const int maxn = + ;
int n, d[maxn];
int ans,cnt,vis[SIZE];

void solve()
{
//对剩下m-1个选择进行枚举
for (int i = ; i < ( << (n - )); i++)
{
int v_num = ;
cnt++;
int s = SIZE / + d[];
//for (int i = 0; i < SIZE; i++) vis[i] = 0; //这种标记会导致T
vis[SIZE / ] = cnt;
vis[SIZE / + d[]] = cnt; //强行规定第一次向左走

     for (int j = ; j < n - ; j++)  
     {  
         if (i & ( << j))  
             s += d\[j + \];  
         else  
             s -= d\[j + \];  
         if (vis\[s\] != cnt)  
         {  
             v\_num++;  
             vis\[s\] = cnt;  
         }  
     }  
     ans = min(ans, v\_num);  
 }  

}

int main()
{
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d", &d[i]);
ans = n + ; //ans不会超过n+1
cnt = ;
solve();
printf("%d\n", ans);
return ;
}

思路二：DFS尝试遍每一种情况

O(2N-1)

#include
#include
#include
#include
using namespace std;

const int SIZE = * * + ; //数轴的范围，SIZE/2相当于原点
const int maxn = + ;
int m, d[maxn];
int vis[SIZE];
int ans;

//第cur+1个状态,x位置，顶点数v
void dfs(int cur, int x, int v)
{
if (cur == m)
{
ans = min(ans, v);
return;
}
int net = x + d[cur];
vis[net]++; //不能只用0/1来区分
dfs(cur + , net, v + (vis[net] == ));
vis[net]--;

 net = x - d\[cur\];  
 vis\[net\]++;  
 dfs(cur + , net, v + (vis\[net\] == ));  
 vis\[net\]--;  

}

int main()
{
while (scanf("%d",&m) == && m)
{
memset(vis, , sizeof(vis));
for (int i = ; i < m; i++)
scanf("%d", &d[i]);
ans = m + ; //ans不会超过m+1
vis[SIZE / ] = ;
vis[SIZE / + d[]] = ; //强行规定第一次向有走
dfs(, SIZE / + d[], );
printf("%d\n", ans);
}
return ;
}