# TLE

// vijos2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <string>
#include <list>
#include <vector>
#include "math.h"
#include <map>
#include <iterator>
#include <bitset>
#include <set>
#include <deque>
#include <stack>
#include <algorithm>

using namespace std;
int work(int,int,int,int,list<int>,int);
int main()
{
list<int> score;
int A, B=0, C=0, D=0,t;
int maxscore;
int N,M;
cin >> N >> M;
for (maxscore = 0;maxscore < N;maxscore++)
{
cin >> A;
score.push_back(A);
}
A = 0;
for (maxscore = 0;maxscore <M;maxscore++)
{
cin >> t;
switch (t){
case (1) :
A++;
break;
case (2) :
B++;
break;
case (3) :
C++;
break;
case (4) :
D++;
}
}
maxscore = 0;
cout << work(A,B,C,D,score,0);
return 0;
}
int max(int a, int b)
{
return (a > b ? a : b);
}
int work(int A, int B, int C, int D, list<int> score,int loc) {
list<int>::iterator ite;
ite = score.begin();
if ((A == 0) && (B == 0) && (C == 0) && (D == 0))
{
ite = score.end();
ite--;
return (ite);
}
int a, b, c, d;
if (A > 0)a = work(A-1,B,C,D,score,loc+1);else a = 0;
if (B > 0)b = work(A, B - 1, C, D, score, loc + 2);else b = 0;
if (C > 0)c = work(A, B, C - 1, D, score, loc + 3);else c = 0;
if (D > 0)d = work(A, B, C, D - 1, score, loc + 4);else d = 0;
int t;
for (t = 0;t < loc;t++)
ite++;
return (max(a, max(b, max(c, d)))) + (
(ite ));
}

# 3 条评论

• @ 2016-08-14 21:43:21

表示这题DFS，BFS都TLE了，DP秒过

• @ 2015-09-27 11:08:33

表示原来不是枚举，是动态规划，，，
// temptest.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <deque>
#include <vector>
#include <cstdlib>
#include <cctype>
#include <cstdio>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <functional>
#include <algorithm>
using namespace std;
int board[360];
int f[41][41][41][41];
int main()
{
memset(board, 0, sizeof(board));
memset(f, 0, sizeof(f));
int m, n;
cin >> m >> n;
for (int i = 0;i < m;i++)
cin >> board[i];
int a, b, c, d;
a = b = c = d = 0;
for (int i = 0;i < n;i++)
{
int t;
cin >> t;
if (t == 1)a++;
if (t == 2)b++;
if (t == 3)c++;
if (t == 4)d++;
}
for (int j = 0;j <= a;j++)
for (int k = 0;k <= b;k++)
for (int l = 0;l <= c;l++)
for (int m = 0;m <= d;m++)
{

if (j != 0)
f[j][k][l][m] = max(f[j][k][l][m],f[j - 1][k][l][m]);
if (k != 0)
f[j][k][l][m] = max(f[j][k][l][m], f[j][k-1][l][m]);
if (l != 0)
f[j][k][l][m] = max(f[j][k][l][m], f[j][k][l-1][m]);
if (m != 0)
f[j][k][l][m] = max(f[j][k][l][m], f[j][k][l][m-1]);
f[j][k][l][m] += board[j + (k << 1) + l * 3 + (m << 2)];
}
cout << f[a][b][c][d];
return 0;
}

• @ 2015-09-08 21:42:33

这题像这样普通的搜索肯定会TLE的。可以尝试一下优化你的搜索算法，比方说想办法减少重复搜索的次数。

• @ 2016-11-10 17:20:53

这道题除了判断后程可以加的最大的分数再判断剪枝外，还有别的搜索优化方法吗

• 1

ID
1775

2

2282

1266

55%

11