hdu 1466 직선의 교점 수 계산

933 단어 dp
수조 dp[i][j]를 사용합니다.만약에 dp[i][j]=1을 놓으면 i개의 직선에 j개의 교점이 있다는 것을 의미한다. 그러면 dp[n][i]를 i=0에서 i=190까지 한 번 쓸어야 한다. 왜냐하면 20개의 직선은 최대 190개의 교점이 있기 때문이다.
이전: i개의 직선에 몇 개의 교점이 있는지 요구하면 이 i개의 직선은 두 조로 나눌 수 있다. 한 조는 j개의 평행선이고 다른 한 조는 i-j개의 자유선이다. 이 교법의 교점수는 (i-j)*j+k(k는 j개의 자유선의 교점수)이다.
#include<stdio.h>
#include<string.h>
int main()
{
    int dp[21][191];
    int n,m,i,j,k;
    memset(dp,0,sizeof(dp));
    for(i=1;i<=20;i++)
    dp[i][0]=1;//   ,   0   ,  dp[i][0]==1
    for(i=1;i<21;i++)
    for(j=0;j<i;j++) //j    ,  i-j      
    {
        for(k=0;k<191;k++)
        if(dp[i-j][k]==1) //i-j       k      , , i             
        dp[i][(i-j)*j+k]=1;
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("0");
        for(i=1;i<191;i++)
        if(dp[n][i])
        printf(" %d",i);
        printf("
"); } return 0; }

좋은 웹페이지 즐겨찾기