本文共 3026 字，大约阅读时间需要 10 分钟。

因为行数很小，我们可以一列一列的考虑。对于每一列的方法要受到前一列的影响，dp[i][j]表示第i列对第i+1列的影响为j的方案数，比如当n=5，j的二进制为01100时，表示当前列的第三个和第四个位置已经被之前占了。我们dfs遍历当前列的每一行。

#include
   
    using namespace std;const int maxn=10;const int maxm=1007;int dp[maxm+7][(1<
    
     0) dfs(l,h+1,cur,nex);  //当前位置被占了，就直接dfs下一行  if(((1<
    
   

dp[i][j]表示经过状态j后在第i个人手中的最小代价。对于状态j，假设总共有5个人，二进制01100表示经过第3和第4个人的状态。

#include
   
    using namespace std;int n;int a[27][27];int dp[20][1<<16];//dp[i][j]表示经过状态j后在i的最小代价int main(){
        freopen("in.txt","r",stdin);     freopen("out.txt","w",stdout);     scanf("%d",&n);     for(int i=0;i
   

dp[i]表示当前选择的字符串的子序列编号状态压缩为i，对于每个状态，再考虑这个状态的字符中是否可以由回文串和剩余串移除。

#include
   
    using namespace std;const int maxn=20;const int inf=0x3f3f;string s;int dp[1<
    
     >=1;    pos++;  }  for(int i=0,j=s2.size()-1;i
     
      >s;  int len=s.length();  for(int i=1;i<(1<
     
    
   

对于每一行，首先用一个数组存该行所有可选的列。然后一行一行的考虑，对于每一行枚举所有选择的，去掉当前选择中选到当前行中不合法的列或者选到了相邻列的，然后遍历上一行选择，如果上一行的选择与这一行起冲突则跳过，否则更新当前行。

自己敲的代码因为上课着急走忘了保存，不想再敲了，放上别人的代码：

#include
   
     using namespace std; const int MAX_N = 20;const int MAX_M = 20;int state[MAX_N + 1];int dp[MAX_N + 1][1 << MAX_M]; bool not_intersect(int now, int prev) {
       return (now & prev) == 0;} bool fit(int now, int flag) {
       return (now | flag) == flag;}bool ok(int x) {
       // 行内自己是否相交    return (x & (x >> 1)) == 0;      //说明没有相邻的点}int count(int now) {
       int s = 0;  // 统计 now 的二进制形式中有多少个 1    while (now) {
           s += (now & 1);  // 判断 now 二进制的最后一位是否为 1，如果是则累加        now >>= 1;  // now 右移一位    }    return s;} int main() {
       int n, m;    cin >> n >> m;    // 初始化所有数组    for (int i = 1; i <= n; ++i) {
           for (int j = 0; j < m; ++j) {
               int flag;            cin >> flag;            state[i] |= (1 << j) * flag;  // 将 (i,j) 格子的状态放入 state[i] 中，state[i] 表示第 i 行的可选格子组成的集合        }    }    for (int i = 1; i <= n; ++i) {
           for (int j = 0; j < (1 << m); ++j) {
     // 枚举当前行的状态            if (!ok(j) || !fit(j, state[i])) {
     // 如果当前行状态不合法则不执行后面的枚举                continue;            }            int cnt = count(j);  // 统计当前行一共选了多少个格子            for (int k = 0; k < (1 << m); ++k) {
                   if (ok(k) && fit(k, state[i - 1]) && not_intersect(j, k)) {
     // 判断前一行是否合法和当前行和前一行的方案是否冲突                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + cnt);  // 更新当前行、当前状态的最优解                }            }        }    }    int ans = 0;  // 保存最终答案    for (int i = 0; i < (1 << m); ++i) {
           ans = max(ans, dp[n][i]);      }    cout << ans << endl;    return 0;}
   

将每一包糖果的状态进行压缩。

#include
   
    using namespace std;const int maxn=107;const int maxm=27;int n,m,k;int t;int d;int dp[1<<20];int a[maxn];int main(){
       freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=n;i++)    {
           d=0;        for(int j=1;j<=k;j++)        {
               scanf("%d",&t);            d=(1<<(t-1))|d;        }        a[i]=d;        dp[d]=1;    }    for(int i=1;i<=n;i++)    for(int j=0;j<(1<
   

转载地址：http://wpgwi.baihongyu.com/