BZOJ2428||낙곡P2503 [HAOI2006] 균등한 데이터 [시뮬레이션 퇴화+DP]

Time Limit: 5 Sec Memory Limit: 128 MB

Description

알려진 N개의 양의 정수: A1, A2,......, An.이제 이를 M그룹으로 나누어 각 그룹의 데이터의 수치와 가장 평균, 즉 각 그룹의 평균 방차를 최소화해야 한다.균일 방차 공식은 다음과 같다.σ균일 방차로 각 그룹의 데이터와 평균값이고 xi는 i조 데이터의 수치와 같다.

Input

첫 번째 줄은 두 개의 정수로 N을 나타내고 M의 값(N은 정수 개수, M은 나누려는 그룹의 수)을 나타낸다. 두 번째 줄은 N의 정수로 A1, A2,......, An을 나타낸다.정수의 범위는 1–50이다.(같은 행의 정수를 공백으로 나누기)

Output

이 줄은 소수점 뒤의 두 자리 숫자를 보존하는 최소 균일 방차의 값을 나타내는 숫자만 포함한다.

HINT

모든 데이터에 대해 K<=N <=20, 2<=K<=6 보장

제목 분석

이 문제의 난점은 같은 조의 숫자가 반드시 연속되는 것은 아니라는 데 있다
만약 그룹이 연속적이라고 가정한다면 우리는 dp[i][j]dp[i][j]dp[i][j]로 전 iii의 수분 jj조의 최소치를 나타낼 수 있다
초기화 dp [0] [0] = 0 dp[0][0] = 0 dp[0][0] = 0,나머지는 i n f inf inf 그렇다면 전이 방정식 dp [i] [j] = m i n (dp [k] [j] [j: 1] + (su m [i]: 1s u m [k] - sm [i] [j] dp[i] [j] = min(\dp[k] [j]] [j] [k] [j]] + (sum[i] - sum[i] - sum[k] - rac [k] - {sum [n] [n] {m[n]} [k] {{m] {{m] [n] {m [n] {m] [j]] [j] [j] [j] [j]] [[j]]] [j] = ([j] [j]] [j] [n]) k∈[0, i)k\in[0, i)k∈[0, i) 그 중에서 sum[i]sum[i]sum[i]는 원 서열 접두사이고 DP의 복잡도는 O(n3)O(n^3)이다 O(n3)
문제를 풀이 연속 숫자의 그룹으로 바꾸기 위해서 우리는 아날로그 퇴화로 끊임없이 무작위로 새로운 서열을 만들고 DP를 사용하여 최상의 결과를 향해 접근할 수 있다

등산 알고리즘 x 시뮬레이션 퇴화

#include
#include
#include
#include
#include
#include
using namespace std;
typedef double dd;
#define sqr(x) ((x)*(x))
#define T 1000
#define eps 1e-8
#define delta 0.993
 
int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}
 
const int maxn=50;
int n,m;
int a[maxn],sum[maxn];
dd dp[maxn][maxn],ans;
 
dd DP()
{
    memset(dp,67,sizeof(dp)); dp[0][0]=0;
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;++i)
    for(int j=1;j<=i;++j)
    for(int k=0;k<i;++k)
    dp[i][j]=min(dp[i][j],(dd)dp[k][j-1]+(dd)sqr((dd)(sum[i]-sum[k])-(dd)sum[n]/m));
    return dp[n][m];
}
 
void SA()
{
    dd t=T; 
    while(t>eps)
    {
        int x=0,y=0;
        while(x==y) x=rand()%n+1,y=rand()%n+1;
        swap(a[x],a[y]);
        dd tt=DP();
        dd dE=ans-tt;
        if(dE>=0) ans=tt;
        else if( exp(dE/t) > (dd)rand()/(dd)RAND_MAX ) ;
        else swap(a[x],a[y]);
        t*=delta;
    }
}
 
int main()
{
    srand(19491001);//                ( 
    n=read();m=read();
    for(int i=1;i<=n;++i) a[i]=read();
     
    ans=DP();
    for(int i=1;i<=3;++i) SA();
    printf("%.2lf",sqrt(ans/(dd)m));
    return 0;
}