面条老师跟牛杠上了这是

本题洛谷传送门

这题一道动态规划，最刚开始设了两层，不过，后来参照题解修正出来的(说白了不是自己的(打脸))

主要核心代码

f[ i ][ j ][ 0 ] = min( f[ i - 1 ][ j ][ 0 ] + d( i - 1 , i ) , min( f[ i - 1 ][ j ][ 1 ] + d( i , j + h1 ) , f[ i ][ j ][ 0 ] ) ) ;
if( j ) f[ i ][ j ][ 1 ] = min( f[ i ][ j ][ 1 ] , min( f[ i ][ j - 1 ][ 1 ] + d( h1 + j , h1 + j - 1 ) , f[ i ][ j - 1 ][ 0 ] + d( i , h1 + j ) ) ) ;

为什么if( j )：f[ i ][ 0 ]没法通过f[ i ][ -1 ]转过来

完整代码:

#include<bits/stdc++.h>
using namespace std ;
long long h1 , g1 , f[ 1001 ][ 1001 ][ 2 ];
int x[ 2001 ] , y[ 2001 ] ;
int d( int i ,int j )
{
	return( x[ i ] - x[ j ] ) * ( x[ i ] - x[ j ] ) + ( y[ i ] - y[ j ] ) * ( y[ i ] - y[ j ] ) ;
}
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    memset( f , 0x3f , sizeof( f ) ) ;
    f[ 1 ][ 0 ][ 0 ] = 0 ;
    cin >> h1 >> g1 ;
    for( int i = 1 ; i <= h1 + g1 ; i ++ )
    {
        int a , b ;
        cin >> a >> b ;
        x[ i ] = a ;
        y[ i ] = b ;
    }
    for( int i = 1 ; i <= h1 ; i ++ )
    {
        for( int j = 0 ; j <= g1 ; j ++ )
        {
            f[ i ][ j ][ 0 ] = min( f[ i - 1 ][ j ][ 0 ] + d( i - 1 , i ) , min( f[ i - 1 ][ j ][ 1 ] + d( i , j + h1 ) , f[ i ][ j ][ 0 ] ) ) ;
            if( j ) f[ i ][ j ][ 1 ] = min( f[ i ][ j ][ 1 ] , min( f[ i ][ j - 1 ][ 1 ] + d( h1 + j , h1 + j - 1 ) , f[ i ][ j - 1 ][ 0 ] + d( i , h1 + j ) ) ) ;
        }
    }
    cout << f[ h1 ][ g1 ][ 0 ] ;
    return 0;
}