ZJU1234 Chopsticks - 동적 계획
한 사람이 새로운 젓가락을 사용하는 방법을 발명했다. 매번 세 개의 젓가락을 사용하면 젓가락의 길이가 같지 않다(A<=B<=C). 세 개의 젓가락을 규정하는'부적정'용(A-B)^2로 표시한다.현재 n개의 길이가 다른 젓가락이 있는데 m부의 젓가락을 고르는 데 가장 작고 적당하지 않은 젓가락의 합이 얼마냐고 묻는다.입력 시 젓가락 길이에 따라 비강하 순서로 입력한다.
분석:
이 동적 기획의 변형은 비교적 이상하다. 세 젓가락의 길이는 가장 길고 그 뿌리는 쓸모가 없지만 반드시 있어야 한다.
수조a[i]는 i번째 젓가락의 길이를 표시하고 비승차순으로 배열하며 1부터 표시한다.상태 f[i][j]로 이전 i뿌리 젓가락에서 j부를 선택하여 얻은 최소 부적합도를 나타낸다.
만약에 제 a[i] 젓가락을 가장 짧은 것으로 선택하면 다음 짧은 젓가락은 반드시 a[i-1]임을 증명할 수 있다.그래서bad(i)는 i번째 젓가락이 가장 짧게 얻은 부적합함을 나타낸다.
분명히, 초기 상태:
f[i][0]=0;f[3][1]=bad(3).
상태 이동 방정식 f[i][j]=min{f[i-1][j], f[i-2][j-1]+bad(i)}.
f[i][j]의 비합법적인 상황을 처리하는 데 주의해야 한다.
/* ZJU1234 Chopsticks */ #include #include #define N 5005 #define K 1005 #define INF 99999999 #define clr(a) memset(a,0,sizeof(a)) #define MIN(a,b) ((a)>(b)?(b):(a)) #define POW(a) ((a)*(a)) int n,m; int a[N]; int f[N][K]; int bad(int i){ return POW(a[i]-a[i-1]); } int main() { int i,j,k,T; int min; scanf("%d",&T); while(T--){ //init clr(a); clr(f); min=INF; //input scanf("%d%d",&k,&n); m=k+8; for(i=n;i>=1;i--) scanf("%d",&a[i]); //DP f[3][1]=bad(3); for(i=4;i<=n;i++){ k=MIN(i/3,m); for(j=1;j<=k;j++){ if(j*3==i) f[i][j]=INF; else f[i][j]=f[i-1][j]; f[i][j]=MIN(f[i][j],f[i-2][j-1]+bad(i)); if(j==m) min=MIN(min,f[i][j]); } } //output printf("%d/n",min); } return 0; }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
