[낙곡P1164] 샤오A 주문.
1698 단어 DP
제목 전송문 P1164
제목 배경
uim 신번은 uoi의ra(라듐표)를 받자마자 기우 A를 끌고 식당에 갔어요. 아주 낮은 거요.uim 벽에 있는 가격표(너무 저급해서 메뉴가 없어)를 가리키며 "마음대로 시키세요."라고 말했다.제목 설명
그러나
uim 약간 （e） （ro） 을 샀기 때문에 주머니에는 MM위안(M≤10000)만 남았다.식당은 비록 저급하지만 메뉴의 종류는 적지 않다. NN종(N\le 100)(N≤100), 제ii종은 aiai원(ai≤1000).아주 낮은 식당이기 때문에 종류별로 1인분만 있습니다.
A'돈을 다 먹지 않으면 그만두지 않는다'고 봉행하기 때문에 그는 주문을 하면 꼭 맞을 것이다uim 몸에 있는 모든 돈을 다 쓴다.그는 몇 가지 주문 방법이 있는지 알고 싶어 한다. A 배가 너무 고파서 최대 11초만 기다려야 한다.입력 출력 형식
입력 형식:
첫 번째 행은 N과 M을 나타내는 두 개의 숫자입니다.
두 번째 줄부터 N개의 정수ai(같은 숫자가 있을 수 있고 모든 숫자가 1000 이내일 수 있다).
출력 형식:
하나의 정수로 주문 방안의 수를 표시하고 답안의 범위가 int 안에 있음을 보증합니다.
출력 샘플 가져오기
샘플 #1 입력:
4 4
1 1 2 2
샘플 내보내기 #1:
3문제풀이
이 문제는 사실 매우 간단해서 문제를 명확하게 분석하기만 하면 쉽게 풀 수 있다.
j=a[i]일 때, 즉 j== 제i요리의 가격 f[i][j]=f[i-1][j]+1;j>a[i]일 때, 즉 j>제i요리의 가격 f[i][j]=f[i-1][j]+f[i-1][j-a[i]];제이
그럼 이제 아주 즐거워요. 그냥 치면 돼요.
AC 코드
#include
using namespace std;
int n, m;
int a[110];
int f[110][10010];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j == a[i]) {
f[i][j] = f[i - 1][j] + 1;
}
else if (j > a[i]) {
f[i][j] = f[i - 1][j] + f[i - 1][j - a[i]];
}
else if (j < a[i]) {
f[i][j] = f[i - 1][j];
}
}
}
cout << f[n][m];
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
