本文主要是介绍POJ2511(今天是个失败的题解,未能AC,求帮忙纠正),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目就是类似背包问题,给容量为10的书架选情感值较大的书,并且这些书相邻的是不能在相同位置是相同的字母。
TLE超时了,今天是个失败的题解,求帮忙呀!
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct node {int val;char pre[101];char cur[101];
}a[2501];
bool cmp(node a, node b)
{if (strcmp(a.cur, b.cur) < 0)return 1;elsereturn 0;
}
bool del(char* a, char* b)
{ int i=0;while (a[i] != '\0' && b[i] != '\0'){if (a[i] == b[i])return true;i++;}return false;
}
int main()
{int n;scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%d",&a[i].val); int sub = 0; int sub1 = 0;char ch;ch = getchar();cin.getline(a[i].pre,100);while((ch=a[i].pre[sub++])!='\0'){if(ch!='\''&&ch!=' '){ if(ch>='A'&&ch<='Z')a[i].cur[sub1++]=ch+32;elsea[i].cur[sub1++]=ch;}}}sort(a, a + n, cmp);vector<node>ans[2501][11];int data[2501][11] = { 0 };for (int i = 1; i <= n; i++){ for (int j = 1; j <= 10; j++){int k = i-1;while (ans[k][j - 1].size() != 0 && del(a[i - 1].cur, ans[k][j - 1][ans[k][j - 1].size() - 1].cur)){ k -= 1;if (k == 0)break;}data[i][j] = data[k ][j - 1] + a[i - 1].val;ans[i][j] = ans[k][j - 1];ans[i][j].push_back(a[i - 1]);if (data[i][j] < data[i - 1][j]){data[i][j] = data[i - 1][j];ans[i][j] = ans[i - 1][j];}}}printf("%d\n%d\n", ans[n][10].size(), data[n][10]);for (int i = 0; i < ans[n][10].size(); i++){printf("%s\n", ans[n][10][i].pre);}return 0;
}
这篇关于POJ2511(今天是个失败的题解,未能AC,求帮忙纠正)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!