糖果问题，输出不正确，找不到原因

Question

糖果问题，为甚麽输出是-1不是2，前面的这段代码错误在哪里？后一个我搜到的可以正确输出，我找不出第一个的错误原因请帮忙看看

#include<bits/stdc++.h>
using namespace std;
//M 种口味 K 颗一包 给定 N 包糖果
int a[101]={0},f[1<<20];
int main()
{
    int n,m,k;

    cin>>n>>m>>k;
    //scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)
     {
         for(int j=0;j<k;j++)
          {
              int t;
              cin>>t;
              //scanf("%d",t[i][j]);
              a[i]=a[i]|(1<<(t-1));
          }
          
     }
     //memset(f,sizeof(f),-1);
     for(int i=1;i<(1<<m);i++)
      f[i]=-1;
     f[0]=0;
     for(int i=0;i<n;i++)
     {
         for(int j=0;j<(1<<m);j++)
         {
             if(f[j]==-1) continue;
              f[j|a[i]]= (f[j|a[i]]<f[j]+1)? f[j|a[i]] : f[j]+1;
         }
     }
    // printf("%d",f[1<<m-1]);
  
    cout<<f[(1<<m)-1];
         return 0;
}

#include <stdio.h>
#include <string.h>
int f[1<<20],a[105]={0};
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int num=(1<<m);    // m种口味的各种组合总的状态数
    int i,j;
    for (i=0;i<num;i++)
    {
        f[i]=105;
    }
    for (i = 0;i<n;i++)
    {
        for (j = 0;j<k;j++)
        {
            int t;
            scanf("%d",&t);
            a[i] = a[i]|(1<<(t-1));
        }
    }
    f[0]=0;
    for (i=0;i<n;i++)
       for (j=0;j<1<<m;j++)
       {
           if (f[j]>100) continue;
           f[j|a[i]]= (f[j|a[i]]<f[j]+1)? f[j|a[i]] : f[j]+1;
       }
    if (f[num - 1]==105) printf("-1");
    else printf("%d",f[num - 1]);
    return 0;
}

Answer 1

让【宝码香车】来帮你解答，本回答参考DeepSeek编写，并整理提供。
如果还有疑问可以点击头像关注私信或评论。如果答案让您满意，请采纳、点赞、关注，非常感谢！

# 糖果问题代码分析

问题分析

你提供的两个代码都试图解决糖果问题，但第一个代码输出不正确（输出-1），而第二个代码能正确输出。我将分析第一个代码的问题所在。

主要区别

两个代码的主要区别在于初始化和边界条件处理：

1. 初始化方式不同：

   • 第一个代码将f[1..(1<<m)-1]初始化为-1
   • 第二个代码将f[0..(1<<m)-1]初始化为105（一个较大的数）

2. 条件判断不同：

   • 第一个代码跳过f[j]==-1的情况
   • 第二个代码跳过f[j]>100的情况

第一个代码的问题

问题出在状态转移的条件判断和初始化上：

f[j|a[i]]= (f[j|a[i]]<f[j]+1)? f[j|a[i]] : f[j]+1;

当f[j|a[i]]为-1（未访问过）时，f[j|a[i]]<f[j]+1比较结果为false（因为-1 < 任何正数），所以会取f[j]+1。这看起来是正确的。

但是，当所有状态都无法到达目标状态(1<<m)-1时，第一个代码会输出初始值-1，而第二个代码会检查是否等于105（它的初始值）来决定输出-1。

具体错误

1. 初始值问题：第一个代码没有正确区分"未访问"和"无法到达"的状态。当目标状态无法到达时，它保持初始值-1。

2. 边界条件处理：第一个代码没有像第二个代码那样显式处理无法到达的情况。

修正建议

将第一个代码修改为类似第二个代码的初始化方式：

// 修改初始化部分
for(int i=1;i<(1<<m);i++)
    f[i] = n+1;  // 使用一个比最大可能值大的数
f[0] = 0;

// 修改输出部分
if(f[(1<<m)-1] > n)
    cout << -1;
else
    cout << f[(1<<m)-1];

为什么第二个代码正确

第二个代码：

1. 使用105作为"无穷大"值（因为n最多100，105肯定大于任何有效解）
2. 明确检查最终结果是否等于初始值来决定输出-1
3. 更清晰地表达了"无法到达"的概念

总结

第一个代码的主要问题是初始化值和边界条件处理不够明确，导致无法正确识别"无法到达"的情况。建议采用类似第二个代码的初始化方式，使用一个明显大于可能解的值作为初始值，并在输出时检查是否仍为该初始值来决定是否输出-1。