uva 10271 Chopsticks
#include<iostream>
#include<algorithm>
#include<map>
#include<string>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<iomanip>
#include<set>
#include<fstream>
#include <climits>
using namespace std;
int dp[5001][1001];
int cho[5001];
int main()
{
ios::sync_with_stdio(false);
int t,k,n;
cin>>t;
while(t--)
{
cin>>k>>n;
k+=8;
for(int i=n;i>=1;i--)
cin>>cho[i];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
dp[i][j]=INT_MAX;
for(int i=3;i<=n;i++)
{
for(int j=1;j<=k;j++)
if(i>=j*3)
dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(cho[i]-cho[i-1])*(cho[i]-cho[i-1]));
}
cout<<dp[n][k]<<endl;
}
// input.close();
// output.close();
return 0;
}
해답: 처음 봤을 때 아직 흐리멍덩하다. 만약에 데이터가 작으면 수동으로 시뮬레이션을 해서 자신의 전이 방정식이 정확한지 확인할 수 있다.그러나 이 데이터는 비교적 커서 수동 시뮬레이션은 매우 힘들다.먼저 상태를 고려한다. n개의 막대기가 k개를 선택하기 때문에 상태가 2차원이라는 것을 쉽게 확인할 수 있다. dp[i][j]로 설정하면 앞의 i개의 막대기가 j조를 선택할 때의 최소badness를 나타낸다.다음에 상태 이동 과정을 보면 먼저 관건적인 점을 생각해야 한다. 사실은 매우 좋다. 왜냐하면 제목에서 이미 힌트를 주었기 때문이다. 바로 너에게 준 데이터는 비강등 순서에 따라 배열되기 때문이다.예를 들어 지금 또 세 개의 수 A, B, C, D가 있는데 A<=B<=C<=D가 있다. 지금 너에게 A, B, C, D 중의 한 개의 수 X를 줄 것이다. 너에게 다른 수 Y를 찾아서 (X-Y)^2를 최소화하라고 한다. 이것은 X와 인접한 두 개의 수를 찾아서 판단하는 것이 분명하다.상태가 이동하는 과정이 유사하여 i번째 막대기를 선택하거나 선택하지 않습니다.dp[i-1][j]로 표시하는 것을 선택하지 않으면 i번 막대기로 j조를 구성하지 않는다는 뜻이다.만약에 i번 막대기를 사용한다면 dp[i-2][j-1]+(cho[i-1]-cho[i])^2는 앞의 i-2개의 막대기로 j-1조를 구성하고 i-1, i-2개의 막대기로 구성된 조의 badness를 나타낸다.(여기서 막대기의 길이 순서를 거꾸로 해야 한다는 것을 기억한다) dp[i][j]=min(dp[i-1][j], dp[i-2][j-1]+(cho[i]-cho[i-1])*(cho[i]-cho[i-1])))).
경계 처리를 주의하면 됩니다~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA 10025(수학)Given the following formula, one can set operators '+' or '-' instead of each '?', in order to obtain a given k ? ? n = ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.