首页 > 代码库 > uva 10559
uva 10559
记忆话搜索 DP
看了网上题解 状态方程真是巧妙 orz
#include <cstdio>#include <cstdlib>#include <cmath>#include <set>#include <stack>#include <vector>#include <sstream>#include <cstring>#include <string>#include <map>#include <queue>#include <algorithm>#include <iostream>#define FFI freopen("in.txt", "r", stdin)#define maxn 210#define INF 0x3f3f3f3f#define inf 10000000#define MOD 1000000007#define ULL unsigned long long#define LL long long#define _setm(houge) memset(houge, INF, sizeof(houge))#define _setf(houge) memset(houge, -1, sizeof(houge))#define _clear(houge) memset(houge, 0, sizeof(houge))using namespace std;int dp[maxn][maxn][maxn];int a[maxn], n;int dfs(int l, int r, int k){ if(l > r) return 0; if(dp[l][r][k]) return dp[l][r][k]; dp[l][r][k] = dfs(l, r-1, 0) + (1+k)*(1+k); for(int i = r-1; i >= l; -- i) { if(a[r] == a[i]) { dp[l][r][k] = max(dp[l][r][k], dfs(l, i, k+1)+dfs(i+1, r-1, 0)); } } return dp[l][r][k];}int main() { FFI; int t, ca = 0; scanf("%d", &t); while(t --) { _clear(dp); scanf("%d",&n); for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]); printf("Case %d: %d\n", ++ ca, dfs(1, n, 0)); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。