UVa:10910 Marks Distribution

1609 단어 점차 미루다
처음에는 계수류의 dp를 사용할 수 있을 것 같았지만 스스로 추측하여 규칙을 발견하여 하나를 썼다...
왜 1과목만 있고 P가 T보다 작을 때는 1이고 왜 0이 아닌지 모르겠어요.(나중에 보니 P는 합격선이고 T는 그의 득점이다. 몇 가지 가능성을 물었다.)
나중에 인터넷에서 보니 역시 계수류의 dp로 추정할 수 있었다.
우선 문제는 i개수로 j의 종류, dp[i][j]로 변환할 수 있다.그리고 상태 이동 방정식 dp[i][j]=dp[i-1][j]+dp[i][j-1]는 dp[i-1][j]의 기초 위에서 각각 뒤에 0을 추가하고 dp[i][j-1]의 기초 위에서 첫 번째 수에 1을 추가한다.
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
#define INF 2139062143
#define MAXN 100005
using namespace std;
int main()
{
    int T;
    //freopen("outttt.txt","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        int n,t,p;
        scanf("%d%d%d",&n,&t,&p);
        int v=t-n*p;
        if(v<0) printf("0
"); else if(n==1) printf("1
"); else { int arr[100]= {0}; v++; for(int i=1; i<=v; ++i) arr[i]=1; int d=n-1; for(int i=1; i<d; ++i) { for(int j=1; j<=v; ++j) arr[j]=arr[j-1]+arr[j]; } int sum=0; for(int i=1; i<=v; ++i) sum+=arr[i]; printf("%d
",sum); } } return 0; }

좋은 웹페이지 즐겨찾기