题目意思;给你一条n长的线段,我们可以将其划分为n*(n+1)/2个子线段。现在要求子线段在坐标轴上的位置不动,将所有的子串进行压缩,不能出现重叠,问最少能够得到几层原n长的线段。
解题思路:当时是我队友搞的这道题,我一向对找规律的题目很头疼,他就是一一枚举发现的规律。
1 #include2 using namespace std; 3 int main() 4 { 5 int n,k,i,a[101]; 6 a[1]=1; 7 a[2]=2; 8 a[3]=4; 9 for(i=4;i<=100;i++)10 {11 k=i*(i+1)/2;///总的子线段数12 a[i]=k-a[i-1];13 }14 while(~scanf("%d",&n))15 {16 printf("%d\n",a[n]);17 }18 return 0;19 }
但其实也可以这样想,最后得到的层次数是原来长度为n的线段的若干条可能还会有部分,又因为每一层的线段都是子串在坐标轴上不动拼接得来的,那么我们将线段分成一个个的坐标上的点,那么出现次数最多的那个点的次数就是层次数!!!
1 #include2 #include 3 using namespace std; 4 int vis[110]; 5 int main() 6 { 7 int n,j,i,k,ans; 8 ans=0; 9 scanf("%d",&n);10 for(i=1; i<=n; i++)11 {12 for(j=i; j<=n; j++)///划分子段13 {14 for(k=i; k<=j; k++)///将子段拆成一个个的点15 {16 vis[k]++;17 }18 }19 }20 for(i=1; i<=110; i++)21 {22 ans=max(ans,vis[i]);23 }24 printf("%d\n",ans);25 return 0;26 }