另一篇题解被
3 5
-31 -33 23 76 39
-55 -23 3 -37 92
11 -34 29 -100 -100
Hack了,提供一个程序等待被Hack
#include<bits/stdc++.h>
namespace OI
{
#define il inline
#define rg register
typedef long long LL;
typedef double D;
typedef long double LD;
using std :: getchar;
using std :: pair;
using std :: make_pair;
using std :: min;
using std :: max;
bool rd ( int &k ){
char c = getchar (); while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) ){ c = getchar (); }
if ( c == EOF ){ return false; } bool neg = false; if ( c == '-' ){ neg = true; k = 0; }else{ neg = false; k = c - '0'; }
c = getchar (); while ( c >= '0' && c <= '9' ){ k = (k<<1)+(k<<3)+c-'0'; c = getchar (); }
if ( neg ){ k = -k; } return true;
}
bool lrd ( LL &k ){
char c = getchar (); while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) ){ c = getchar (); }
if ( c == EOF ){ return false; } bool neg = false; if ( c == '-' ){ neg = true; k = 0; }else{ neg = false; k = c - '0'; }
c = getchar (); while ( c >= '0' && c <= '9' ){ k = (k<<1)+(k<<3)+c-'0'; c = getchar (); }
if ( neg ){ k = -k; } return true;
}
const int N = 125;
int f [N][N], pos [N], val [N][N];
pair <int,int> pre [N][N];
int F ( int fa, int va ){
if ( f [fa][va] != 0xcfcfcfcf ){ return f [fa][va]; }
for ( rg int i = max ( 0, fa-1 ); i <= va-1; ++i ){
LL temp = F ( fa-1, i ) + val [fa][va];
if ( temp > f [fa][va] ){
f [fa][va] = temp;
pre [fa][va] = make_pair ( fa-1, i );
}
}
return f [fa][va];
}
void Main (){
memset ( f, 0xcf, sizeof ( f ) );
int n, m; rd ( n ); rd ( m );
for ( rg int i = 0; i <= m; ++i ){ f [0][i] = 0; }
for ( rg int i = 1; i <= n; ++i ){
for ( rg int j = 1; j <= m; ++j ){
rd ( val [i][j] );
}
}
int maxI = n;
for ( rg int i = n+1; i <= m; ++i ){ if ( F ( n, i ) > F ( n, maxI ) ){ maxI = i; } }
printf ( "%d\n", F ( n, maxI ) );
rg int temp [2]; temp [0] = n; temp [1] = maxI;
while ( temp [0] && temp [1] ){
pos [ temp [0] ] = temp [1];
pair <int,int> next = pre [ temp [0] ][ temp [1] ];
temp [0] = next.first; temp [1] = next.second;
}
for ( rg int i = 1; i <= n; ++i ){ printf ( "%d ", pos [i] ); }
}
}
using std :: freopen;
int main (){
// freopen ( "data.in", "r", stdin );
// freopen ( "out.out", "w", stdout );
OI::Main();
return 0;
}