比赛时想偏了！不过我觉得我比赛时想的那种方向是没错的。不过边界值应该很难考虑！ 后来讨论时发现他们那种想法很好，写写： 题目意思是给你n条线，n条线有m个交点，要你求出这样的线能将平面分成多少区域！ 首先 n条线最多有 (n-1)*n/2;个点 最多能划分成(n+1)*n/2区域 分别记为maxd。maxs 观察可得出规律：每减少一个点，就减少一个区域/ 所以n条线m个交点能分平面的区域数为：maxs-maxd+m+1; 问题解决。接下来就是判断存不存在这样的n条线有m个交点 这就换成了一个DP问题 f[i][j]记录的是i条线能否有j个交线，若有存1，若无存0； 则有 如果f[i][j]=1; 则f[i+k][j+ki]=1  k=1,2,3.........(就相当于在i条线上加k条平行线能得的点数) 依次填表。代码如下： #include<stdio.h>int f[101][20000];int main(){  int N=0;    int maxd,maxs,m,n,k,i,res;    int max,j; f[0][0]=1; f[1][0]=1; f[2][0]=1; f[2][1]=1; for(i=3;i<101;++i)    { // f[i][1]=1;        //for(j=i;j)        for(k=i-1;k>=0;--k)        {            for(m=0;m<=(k)*(k-1)/2;++m)                if(f[k][m]==1)                    f[i][(i-k)*k+m]=1;        }    }  while(scanf("%d%d",&n,&m)!=EOF)    {        if(n==0&&m==0) break;        N++;  if(f[n][m]!=1)    printf("Case %d: %d lines cannot make exactly %d crossings.\n",N,n,m);  else   {   maxd=(n-1)*n/2;   maxs=(n+1)*n/2;   res=maxs-maxd+m+1;   printf("Case %d: %d lines with exactly %d crossings can cut the plane into %d pieces at most.\n",N,n,m,res);//    printf("%I64d\n",f(n,m));  }  }   return 0;}

评论