1

我对这个任务有疑问。http://www.spoj.com/problems/LINEUP/看起来很简单，但我的解决方案失败了。我得到错误的结果。任何人都可以帮助弄清楚吗？非常感谢您的帮助。:-)

#include <cstdio>
#include <string.h>
using namespace std;

int n;
int prob[21][21];

char vec_rijesio[1<<13];
int memo[1<<13];
int rijesi( int d, int s ) {
   if ( d == 11 )
     {
       return 0;
     }
   if ( vec_rijesio[s] ) return memo[s];
   vec_rijesio[s] = 1;
   int &ret = memo[s];
   ret = 0;

   for ( int i=0; i<11; ++i )
      if ( ( s & (1<<i) ) == 0 ) {
         int tmp = prob[d][i] + rijesi(d + 1, s|(1<<i));
         if ( tmp > ret ) ret = tmp;
      }

   return ret;
}

int main() {
   scanf( "%d", &n );
   for(int o=0;o<n;++o)
   {
   for ( int i=0; i<11; ++i )
      for ( int j=0; j<11; ++j ) {
         int x;
         scanf( "%d", &x );
         prob[i][j] = x;
      }

   int ret = rijesi( 0, 0 );
   printf( "%d\n", ret);
   memset (memo,0,sizeof(memo));
   memset (vec_rijesio,0,sizeof(vec_rijesio));
   }
   return 0;
}
4

2 回答 2

1

问题是分配问题。只需使用匈牙利算法否定优势并最大限度地减少总体劣势。你可以google一下。

零强度将成为非常高的正弱点。

于 2013-10-26T20:24:11.653 回答
0

“所有位置都必须被占据，但是，不要让球员处于他们不擅长的位置（即得分为 0）。”

您应该在这里检查 prob[d][i] != 0 是否：

int tmp = prob[d][i] + rijesi(d + 1, s|(1<<i));

其余的似乎还不错。

于 2013-10-26T20:17:00.820 回答