북화대학 제5 회 프로 그래 밍 경기 봄 리그 D 문제

D - 최대 수익 시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 262144 K, 기타 언어 524288 K 64bit IO Format:% lld 제목 설명
어느 날 수업 시간 에 L 선생님 이 음식 을 가 져 와 서 친구 들 에 게 나 누 어 먹 으 려 고 하 자 이 음식 들 은 n 더미 로 나 뉘 었 습 니 다.모든 무 더 기 는 그것 에 가 치 를 표시 했다.엘 선생님 은 학생 들 에 게 시식 순 서 를 어떻게 선택 하여 시식 의 가 치 를 가장 크게 하 는 지 물 었 다.똑똑 한 당신 은 모든 음식 을 한 번 맛 보 는 것 이 가장 가치 가 있다 는 것 을 바로 생각 했 습 니 다.이때 작은 L 선생님 은 바로 이웃 의 두 가지 음식 을 맛 보지 못 하 는 규칙 을 추가 했다. 예 를 들 어 음식 A B C 가 차례대로 책상 위 에 놓 여 있 는데 음식 A 를 맛 보면 음식 B 를 맛 볼 수 없다.다음 에 맛 볼 음식 은 C 밖 에 없어 요.음식 B 를 맛 보 았 을 때 음식 C 를 맛 볼 수 없고 음식 A 도 맛 볼 수 없다.똑똑 한 당신 은 왼쪽 에서 오른쪽으로 맛 볼 음식 을 선택 하 는 방법 을 알 고 있 습 니 다!가장 큰 가 치 는 얼마 입 니까?
입력 설명: 첫 줄 의 정수 T (1 ≤ T ≤ 500) 는 모두 T 조 테스트 데 이 터 를 표시 합 니 다.각 조 의 데이터 에 대해 첫 번 째 숫자 n (1 ≤ n ≤ 1000) 은 n 더미 의 음식 다음 줄 에 n 개의 수가 있 음 을 나타 내 고 각 더미 의 음식 가치 ai (0 ≤ ai ≤ 100) 를 나타 낸다.
출력 설명: 하나의 정 수 를 출력 하면 얻 을 수 있 는 최대 가 치 를 나 타 냅 니 다.
예시 1
입력 2, 4, 1, 2, 3, 4, 3, 2, 3, 0 출력
6. 3 사례 를 설명 한다. 첫째, 두 번 째 음식 과 네 번 째 음식 을 먹 으 면 얻 는 가치 의 총 계 는 6 이다.
사고방식: DP, i 번 째 위치 에서 두 가지 선택 이 있 습 니 다. 취, 불 취, 취 하면 i - 1 번 째 는 취 할 수 없습니다. 따라서 총 가 치 는 dp [i - 2] + a [i] 입 니 다. 취하 지 않 으 면 총 가 치 는 dp [i - 1] 다음은 ac 코드 입 니 다.

#include 
#include
using namespace std;
 
int a[1010];
int dp[1010];
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            dp[i] = 0;
        }
        dp[0] = 0;
        dp[1] = a[1];
        for(int i = 2; i <= n; i++){
            dp[i] = max(dp[i-2] + a[i], dp[i-1]);
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}