Dynamic Programming?
2183 단어 dp
Dynamic Programming, short for DP, is the favorite of iSea. It is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable to problems exhibiting the properties of overlapping sub-problems which are only slightly smaller and optimal substructure.
Ok, here is the problem. Given an array with N integers, find a continuous subsequence whose sum’s absolute value is the smallest. Very typical DP problem, right?
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case includes an integer N. Then a line with N integers Ai follows.
Technical Specification
1. 1 <= T <= 100
2. 1 <= N <= 1 000
3. -100 000 <= Ai <= 100 000
Output
For each test case, output the case number first, then the smallest absolute value of sum.
Sample Input
2
2
1 -1
4
1 2 1 -2
Sample Output
Case 1: 0
Case 2: 1
문제 풀이:
매 수의 dp값을 현재 값으로 설정하고, 매번 뒤로 한 자리를 추가하고, 마지막으로 최소 값을 선택합니다.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define inf 9999999
using namespace std;
int dp[1005][1005];
int e[1005];
int main(){
int T,k=0;
cin >> T;
while(T--){
k++;
int n;
cin >> n;
for(int i=1;i<=n;i++){
scanf("%d",&e[i]);
}
memset(dp,inf,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i][i]=e[i];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
dp[i][j]=dp[i][j-1]+e[j];
}
}
int mixn=99999999;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(mixn>abs(dp[i][j]))
mixn=abs(dp[i][j]);
}
}
printf("Case %d: %d
",k,mixn);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
