poj3666Making the Grade [dp 이산화]
방정식: dp[i][j]=abs(j-a[i])+mni는 어느 위치로 밀어붙였는지, j는 현재의 최대치(이 데이터는 만족만 하고 줄지 않으면 된다), mn은 앞의 각 최대치를 나타낼 때 소비하는 최소치를 나타낸다.그리고 이산화된 사상은 주어진 데이터의 단일 값이 그렇게 크면 나는 순서를 정하고 대응하는 위치로 대응하는 위치의 수를 대체하는 것이 낫다는 것이다.힘내세요.
p.s. 이틀 만에 매일 밤 이 문제를 생각하고 오랫동안 잠을 이루지 못해 깨달음이 부족함을 느꼈습니다. 그래서 섣달 그
왜 이중 순환 내부가 현재 이 분의 차치인지에 대해 nn, 즉 현재 대순환의 최소치를 추가합니다.
또 이중 순환에 최소치가 나타난 후에 규칙을 발견할 수 있다===대순환 중의 작은 순환에 있어 dp의 가치 크기는 먼저 내려가고 다시 증가할 수 있다(이산화된 좌표가 아닌 j의 값을 먼저 고려하는 경우 j값은 최대치가 아니다) 우리는 원리적으로 분석했다. 이번 순환에서만약에 최소치가 나타난 곳이 지난번 최소치의 뒤에 나타난다면 말할 것도 없다. 나는 현재 이 지난번 순환의 dp값에 이번 차치를 더할 수 없다. 나는 분명히 지난번에 나타난 최소값에 이번 차치를 더해야 한다==지난번에 나타난 최소치의 위치가 이번보다 작기 때문이다. 나는 지난번 순환의 최소값에 굳이 나의 이번 순환의 최소치 그 위치에 추가할 필요가 없다. 전번보다 작으면 된다.
/************
hdu3666
2016.2.5
31656K 157MS C++ 780B
************/
#include
#include
#include
#include
#define Abs(a) ((a)>0?(a):-(a))
using namespace std;
int a[2004],b[2004],n;
long long dp[2004][2004],mn;
int main()
{
// freopen("cin.txt","r",stdin);
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++) {scanf("%d",&a[i]);b[i]=a[i];}
sort(b+1,b+n+1);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
mn=dp[i-1][1];
for(int j=1;j<=n;j++)
{
mn=min(mn,dp[i-1][j]);
dp[i][j]=Abs(a[i]-b[j])+mn;
}
}
mn=dp[n][1];
for(int i=1;i<=n;i++) if(mn>dp[n][i]) mn=dp[n][i];
printf("%I64d
",mn);
}
return 0;
}
좋은 웹페이지 즐겨찾기
