uva 10118,记忆化搜索

时间:2023-01-29 13:30:41

这个题debug了长达3个小时,acm我不能放弃,我又回来了的第一题!

一开始思路正确,写法不行,结果越改越乱

看了网上某神的代码,学习了一下

coding+debug:4小时左右,记忆化搜索+dp类型第一题

/*
* Author: Bingo
* Created Time: 2015/3/2 21:23:20
* File Name: uva10118.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
using namespace std;
const int maxint = -1u>>;
int dp[][][][];
int a[][];
int f[];
int n;
int ans;
int ok(int i,int j,int p,int q){
int m[];
memset(m,,sizeof(m));
int top=;
for (int t=;t<i;t++)
m[top++]=a[][t];
for (int t=;t<j;t++)
m[top++]=a[][t];
for (int t=;t<p;t++)
m[top++]=a[][t];
for (int t=;t<q;t++)
m[top++]=a[][t];
sort(m,m+top);
int cnt=,tans=;
for (int t=;t<top;){
if (m[t]==m[t+]){
tans++;
t+=;
}else {
cnt++;
t++;
}
}
if (cnt<=){
ans=max(ans,tans);
return ;
}
return ;
}
int dfs(int i,int j,int p,int q){
if (i==n&&j==n&&p==n&&q==n) return ;
if (i<n){
i++;
if(ok(i,j,p,q)) {
if (dp[i][j][p][q]){
ans=max(ans,dp[i][j][p][q]);
dp[i][j][p][q]=ans;
}else {dp[i][j][p][q]=ans;dfs(i,j,p,q);}
}
}
if (j<n){
j++;
if(ok(i,j,p,q)) {
if (dp[i][j][p][q]){
ans=max(ans,dp[i][j][p][q]);
dp[i][j][p][q]=ans;
}else {dp[i][j][p][q]=ans;dfs(i,j,p,q);}
}
}
if (p<n){
p++;
if(ok(i,j,p,q)) {
if (dp[i][j][p][q]){
ans=max(ans,dp[i][j][p][q]);
dp[i][j][p][q]=ans;
}else {dp[i][j][p][q]=ans;dfs(i,j,p,q);}
}
}
if (q<n){
q++;
if(ok(i,j,p,q)) {
if (dp[i][j][p][q]){
ans=max(ans,dp[i][j][p][q]);
dp[i][j][p][q]=ans;
}else {dp[i][j][p][q]=ans;dfs(i,j,p,q);}
}
}
}
int main () {
while(cin>>n&&n){
for (int i=;i<n;i++) {
cin >> a[][i]>>a[][i]>>a[][i]>>a[][i];
}
memset(dp,,sizeof(dp));
ans=;
memset(f,,sizeof(f));
//ok(3,3,3,3);
dfs(,,,);
cout << ans<<endl;
}
return ;
}