2054 : 油田
（一个神奇的功能：点击上方文字进入相应页面）
时间限制:1 Sec 内存限制:32 MiB
提交:49 答案正确:6
在太平洋的一片海域，发现了大量的油田！
为了方便开采这些能源，人们将这些油田从1到n进行编号，
人们在开采这些油田时，有三种开采方式，分别为方式A，方式B，方式C。
用不同的方式去开采这些油田所消耗的资金不同，为了防止共振导致的油井坍塌，相邻编号的油田不能使用同一种开采方式。
我们希望你求出开采这n个油田所需要消耗的最小资金，并输出开采每个油田所采用的方式。
先输入一个整数T（0 < T <= 100）,代表有T组测试数据。对于每组数据，第一行输入一个正整数n（n<1000）代表油田数目，
接下来n行，每一行包含三个整数。第i（2 <= i <= n+1）行的这三个数代表着开采编号为i-1的油田分别采用A,B,C三种方式开采所消耗的资金。
对于每一组测试样本，先输出样本编号，接下来输出一个整数，代表着开采这n个油田所需要消耗的最小资金，然后按编号从小到大的顺序输出开采每个油田所采用的方式。每一组测试样本的输出占一行。
复制
1
2
4 8 3
2 1 4
复制
Case 1: 4 CB
看着像是搜索题目，但是时间复杂度太大了，最坏的情况会严重超时！如下：
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define N 1009
const int inf=0x3f3f3f3f;
int ans,n,tem[N],road[N],cost[N][]; //tem中 1A ,2B ,3C
void factroad()
{
int i,j,k;
for(i=;i<=n;i++)
road[i]=tem[i];
return ;
} void dfs(int sum,int step) //step表示当前！
{
if(step==n+)
{
if(ans>sum)
{
ans=sum;factroad();
}
return ;
}
for(int i=;i<=;i++) //当前step的三种选择
{
if(i!=tem[step-])
{
tem[step]=i;
dfs(sum+cost[step][i],step+);
}
}
} int main()
{
int i,j,k,m,T,cas=;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
//memset(vis,0,sizeof(vis));
for(i=;i<=n;i++)
scanf("%d%d%d",&cost[i][],&cost[i][],&cost[i][]);
ans=inf;
dfs(,);
printf("Case %d: %d ",++cas,ans);
for(i=;i<=n;i++)
printf("%c",'A'+road[i]-);
printf("\n");
} return ;
}
该题正解，如下：
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define N 1009
const int inf=0x3f3f3f3f;
int sum; //保存最终最小和
int ans[N]; //ans数组记录最优答案路径
int n,c[N][]; // c数组中c[i][j]表示第i个油田的第j种开采方式的花费
int dp[N][]; //dp数组用于动态规划查找最优解；
//dp[i][j]表示第i个油田采用第j种开采方式时，整个1--i个油田需要的最小开销总和
int pre[N][]; //pre前缀数组用于保存dp过程中的路径 void fact(int x,int y) //输出路径到ans数组里
{
sum=dp[x][y];
while(x>=)
{
ans[x-]=pre[x][y];
y=pre[x][y];
x--;
}
}
void test(int n){ //简单的调试函数
/* for(int i=1;i<=n;i++)
printf("%3d",i);
printf("\n");*/
for(int i=;i<=n;i++)
{
printf("i%d: ",i);
for(int j=;j<=n;j++)
printf("%3d",dp[i][j]);
printf("\n");
}
}
int main()
{
int i,j,k,m,T,cas=;
scanf("%d",&T);
while(T--)
{
memset(c,,sizeof(c)); //这里很重要，C++里数组不赋初值！在下面程序中会访问到c[n+1][]数组里的数
scanf("%d",&n);
//memset(vis,0,sizeof(vis));
for(i=;i<=n;i++)
scanf("%d%d%d",&c[i][],&c[i][],&c[i][]);
memset(dp,,sizeof(dp)); //dp[0][]数组里的数会用到 for(i=;i<=n+;i++)
{
for(j=;j<=;j++) //
{
if(j==)
{
dp[i][j]=c[i][j]+min(dp[i-][],dp[i-][]);
if(dp[i-][]>dp[i-][]) //记录路径，这个没法同上一步用min（）
pre[i][j]=; //这里歪打正着了，存在相等时要选择编号小的记录入路径，不然会出错
else
pre[i][j]=; }
else if(j==)
{
dp[i][j]=c[i][j]+min(dp[i-][],dp[i-][]);
if(dp[i-][]>dp[i-][])
pre[i][j]=;
else
pre[i][j]=;
}
else
{
dp[i][j]=c[i][j]+min(dp[i-][],dp[i-][]);
if(dp[i-][]>dp[i-][])
pre[i][j]=;
else
pre[i][j]=;
}
}
} int minn=min(dp[n+][],min(dp[n+][],dp[n+][])); //找到最小值
if(minn==dp[n+][])
fact(n+,);
else if(minn==dp[n+][])
fact(n+,);
else
fact(n+,);
printf("Case %d: %d ",++cas,sum);
for(i=;i<=n;i++)
printf("%c",ans[i]+'A'-);
printf("\n");
// test(n);
} return ;
}