题目描述

平面上有N条直线，且无三线共点，那么这些直线能有多少不同的交点数？

输入格式

一个正整数N

输出格式

一个整数表示方案总数

输入输出样例

输入 #1复制

4

输出 #1复制

5

说明/提示

N<=25

 

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int n,ans,m;bool dp[30][400];int main(){ scanf("%d",&n); m=(n-1)*n/2; for(int i=1;i<=n;i++){ dp[i][0]=true; } for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k=1;k<=n-i;k++){ dp[i+k][j+k*i]|=dp[i][j]; } } } for(int i=0;i<=m;i++){ if(dp[n][i]){ ans++; } } printf("%d",ans); return 0;}
           
          
         
        
       
      

　　

对p条直线分情况讨论平行线的条数，已知在有r条平行线时有（p-r）条线与他们相交于p*（p-r）个交点，再加上对于这p-r个交点的相交组合即可。