首页 > 代码库 > HDU 1466

HDU 1466

2024-07-08 19:38:38   222人阅读

经典DP，这样的递推确实有点难。 把所有直线分成两组，可以知道

m条直线的交点方案数 =（m-r）条平行线与r条直线交叉的交点数  + r条直线本身的交点方案 

亦就是  =（m-r）*r+r条之间本身的交点方案数（0<=r<m）；

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4  5 bool ans[25][250]; 6  7 int main(){ 8     memset(ans,false,sizeof(ans)); 9     for(int i=1;i<=20;i++){10         ans[i][0]=true;11         for(int r=0;r<=i;r++){12             for(int k=0;k<=r*(r-1)/2;k++)13             if(ans[r][k]){14                 ans[i][(i-r)*r+k]=true;15             }16         }17     }18     int n;19     while(scanf("%d",&n)!=EOF){20         bool flag=false;21         for(int i=0;i<=n*(n-1)/2;i++){22             if(flag){23                 if(ans[n][i])24                 printf(" %d",i);25                 continue;26             }27             else if(ans[n][i]){28                 flag=true;  printf("%d",i);29             }30         }31         printf("\n");32     }33     return 0;34 }
View Code

 


联系
我们