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
分类
动态规划 点击显示
标签
递交数
2287
已通过
1271
通过率
56%
被复制
13
上传者