题解分析

这是一个关于原子能级选择的优化问题，解题的关键在于利用树形动态规划来求解最大独立集问题。

题目理解

科学家需要选择一些原子的能级，使得：

1. 没有两个原子处于相同能级
2. 没有两个原子可以通过发射或吸收一个光子后达到相同能级
3. 所选原子的总能量最大

问题转换

我们可以将每个能级看作图中的一个节点，如果两个能级之间的能量差恰好等于给定的某个光子能量，则在这两个节点之间连一条边。题目要求的就是在这个图中选择一些节点，使得这些节点之间没有边相连，并且总能量最大。

关键观察

题目中提到原子在状态间跃迁时路径是唯一的，并且往返路径互为逆序。这暗示了这个图实际上是一棵树，因为只有树结构满足路径唯一性和往返路径逆序的性质。

算法思路

1. 构建图：将每个能级作为节点，根据能级差是否等于给定的光子能量来构建边。
2. 树形动态规划：在树上求解最大独立集问题。每个节点有两种状态：选或不选，通过深度优先搜索来递推计算这两种状态下的最大能量。

代码实现

#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
 
using std::map;
using std::vector;
#define maxn 205
 
map<int, int> hash;
int node[maxn];
int diff[maxn];
vector<int> G[maxn];
int  dp[maxn][2];
bool vis[maxn];
int n, m;
 
void read(){
    hash.clear();
    for(int i = 0; i <= n; i ++){
        G[i].clear();
    }
    memset(dp, 0, sizeof(dp));
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i ++){
        int a;
        scanf("%d", &a);
        hash[a] = i;
        node[i] = a;
    }
    for(int i = 1; i <= m; i ++){
        scanf("%d", &diff[i]);
    }
}
 
inline int max(int x, int y){
    return x > y ? x : y;
}
 
void dfs(int v, int f){
    for(int i = 0; i != G[v].size(); i ++){
        int u = G[v][i];
        if(u == f)
            continue;
        dfs(u, v);
        dp[v][0] += max(dp[u][1], dp[u][0]);
        dp[v][1] += dp[u][0];
    }
    dp[v][1] += node[v];
}

void solve(){
    //build the tree
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(hash.count( node[i] + diff[j] )){
                G[i].push_back(hash[ node[i] + diff[j] ]);
            }
            if(hash.count( node[i] - diff[j] )){
                G[i].push_back(hash[ node[i] - diff[j] ]);
            }
        }
    }
    dfs(1, -1);
    printf("%d\n", max(dp[1][0], dp[1][1]));
}
 
int main(){
    while(scanf("%d%d", &n, &m), n + m){
        read();
        solve();
    }
    return 0;
}

代码解释

1. 输入处理：read函数读取输入数据，包括能级和光子能量，并初始化数据结构。
2. 图的构建：solve函数根据能级差和光子能量构建图的邻接表。
3. 动态规划：dfs函数通过深度优先搜索实现树形动态规划，计算每个节点选或不选时的最大能量。
4. 结果输出：在主函数中循环处理每个测试用例，调用read和solve函数完成计算并输出结果。

这个算法的时间复杂度是O(N^2*M)，其中N是能级数量，M是光子数量。对于题目给定的约束条件，这个复杂度是可以接受的。