낙곡P1164 작은 A 주문(dp)

1785 단어 dp

제목 배경

uim 신번은 uoi의ra(라듐표)를 받자마자 기우 A를 끌고 식당에 갔어요. 아주 낮은 거요.uim 벽에 있는 가격표(너무 저급해서 메뉴가 없어)를 가리키며 "마음대로 시키세요."라고 말했다.

제목 설명


그러나uim약간 （e） （ro） 샀기 때문에주머니에는MM위안(M\le10000)(M≤10000)만 남았다.
식당은 비록 저급하지만 메뉴의 종류는 적지 않다. NN종(N\le 100)(N≤100), 제ii종은 aiai원(a i\le 1000)(ai ≤ 1000).아주 낮은 식당이기 때문에 종류별로 1인분만 있습니다. A'돈을 다 먹지 않으면 그만두지 않는다'고 봉행하기 때문에 그는 주문을 하면 꼭 맞을 것이다uim 몸에 있는 모든 돈을 다 쓴다.그는 몇 가지 주문 방법이 있는지 알고 싶어 한다. A 배가 너무 고파서 최대 11초만 기다려야 한다.

입력 출력 형식


입력 형식:
 
첫 번째 행은 NN과 MM을 나타내는 두 개의 숫자입니다.
두 번째 줄부터 NN개의 정수 aiai.
 
출력 형식:
 
주문 방안의 수를 표시하는 정수로 답안의 범위가 intint 안에 있음을 보증합니다.
 

출력 샘플 가져오기


샘플 입력 #1: 복사
4 4
1 1 2 2

출력 예제 #1: 복사
3

문제풀이 사고방식: 01배낭에 가득 채울 수 있는 문제풀이, dp[0]=1과 비교하면 현재 요리는 주문하거나 주문하지 않을 수 있기 때문에 안쪽의 순환은 역순입니다.
현재 가방의 용량은 jdp[j]입니다. 용량이 j인 가방은 몇 가지 방법이 있습니다.할 수 있어. 전이 방정식으로.
#include
#include
#include
#include
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define sca(x) scanf("%d",&x)
#define per(i,j,k) for(int i=j;i>=k;i--)
#define inf 0x3f3f3f3f
int v[105];
int dp[10005];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    rep(i,1,n)
    {
        scanf("%d",v+i);
    }
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    rep(i,1,n)
    {
        per(j,m,v[i])
        {
            if(dp[j-v[i]]>0)
            {
                dp[j]+=dp[j-v[i]];
            }
        }
    }
    cout<

SDOI 2017 나무 자르기 게임
Kafka 설치/케이스 실행/Java에서 실행/신뢰성 & 처리량 향상 대책 검토

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage