UVA 10159
http://blog.csdn.net/metaphysis/article/details/6926997
先向作者表达一下敬佩吧，十分巧妙地利用了状态压缩。
这道题有点组合数学的味道，当一个格子选后，就把行最大值与格子值相等的行标志位置1.这样，当111111111111即是求的状态了。
这样，可以设一个sum[MAX-1]的数组来对应每一种状态，通过位的或运算的关系来实现状态转移。实在妙极。
原作者代码：
// [解题方法]
// 根据每个小格所属行的限制来确定该小格内的最大值，然后检测是否满足每行的最大值要求，若不满足，则
// 不可能，若满足，求其最大值。对于最小可能值，可以通过动态规划来获得。
#include
#include
#include
using namespace std;
#define MAXLINES 12 // 行数。
#define MAXCELLS 48 // 小格总个数。
#define MAXINT 10
#define EMPTY (-1)
#define MAXTYPES (1 << 12)
int maxValue[MAXLINES]; // 每行的最大值。
int cells[MAXCELLS]; // 小格内数字值。
// 每个小格属于那些行，行使用题目所给的 A - I 表示。从 0 开始，按从上到下，从左至右的顺序编号。
string belongs[MAXCELLS] = {
"EL", //
"EK", "EL", "FL", // 1 - 3
"AI", "AI", "AJ", "AEJ", "AEK", "AFK", "AFL", "AGL", "AG", "AH", "AH", // 4 - 14
"BI", "BEI", "BEJ", "BFJ", "BFK", "BGK", "BGL", "BHL", "BH", // 15 - 23
"CE", "CEI", "CFI", "CFJ", "CGJ", "CGK", "CHK", "CHL", "CL", // 24 - 32
"DE", "DE", "DF", "DFI", "DGI", "DGJ", "DHJ", "DHK", "DK", "DL", "DL", // 33 - 43
"GI", "HI", "HJ", // 44 - 46
"HI" //
};
// 非 EMPTY 元素值表示组成该行的小格编号，从 0 开始，按从上到下，从左至右的顺序编号。
int lines[MAXLINES][MAXLINES - ] = {
{ , , , , , , , , , , },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , , },
{ , , , , , , , , , , },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , , },
{ , , , , , , , , , , },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , , }
};
// 动态规划求最小可能值，这里使用了 tmp
// 数组，在原 sum 数组计算的结果先填写在 tmp 数组上，以免持续在 sum 数组上操作引起混乱，同时
// 注意最小可能值方案一定是将最大可能值方案中某些小格置 0 而得来的（为什么这样，可以思考一下！）。
int dynamic_programming()
{
int sum[MAXTYPES], tmp[MAXTYPES];
// 初始化。
memset(sum, EMPTY, sizeof(sum));
// 当无任何行匹配时，和最小值为 0.
sum\[\] = ;
for (int i = ; i < MAXLINES; i++)
{
// 在副本上操作。
memcpy(tmp, sum, sizeof(sum));
for (int j = ; j < MAXTYPES; j++)
if (sum\[j\] > EMPTY)
{
for (int k = ; k < MAXLINES - ; k++)
{
// 空小格，该行已处理完毕。
if (lines\[i\]\[k\] == EMPTY)
break;
// 只需处理值为该行最大值的小格。
if (cells\[lines\[i\]\[k\]\] == maxValue\[i\])
{
int t = j;
// cell 表示该小格属于哪些行。
string cell = belongs\[lines\[i\]\[k\]\];
for (int c = ; c < cell.length(); c++)
// 注意条件！只有当小格的值满足了某行的最大值要求，才计
// 入 t。t 的意义是该小格值满足了哪些行的最大值要求。
// 使用匹配的行的序号作为移位值来生成一个唯一表示该行的
// 整数。
if (cells\[lines\[i\]\[k\]\] == maxValue\[cell\[c\] - 'A'\])
t = t | ( << (cell\[c\] - 'A'));
// 更新和的最小值。
if (tmp\[t\] > EMPTY)
tmp\[t\] = min(tmp\[t\], sum\[j\] + maxValue\[i\]);
else
tmp\[t\] = sum\[j\] + maxValue\[i\];
}
}
}
// 获得副本上的结果。
memcpy(sum, tmp, sizeof(tmp));
}
return sum\[MAXTYPES - \]; }
int main(int ac, char *av[])
{
string line;
while (getline(cin, line))
{
// 读入每行的最大值限制。
istringstream iss(line);
for (int i = ; i < MAXLINES; i++)
iss >> maxValue\[i\];
// 根据限制，获得每个方格的最大值。
memset(cells, , sizeof(cells));
for (int i = ; i < MAXCELLS; i++)
{
int value = MAXINT;
for (int j = ; j < belongs\[i\].length(); j++)
value = min(value,
maxValue\[belongs\[i\]\[j\] - 'A'\]);
cells\[i\] = value;
}
// 检查方格的值是否满足最大值要求。
bool noSolution = false;
for (int i = ; i < MAXLINES; i++)
{
int tmp = ;
for (int j = ; j < MAXLINES - ; j++)
{
if (lines\[i\]\[j\] == EMPTY)
break;
tmp = max(tmp, cells\[lines\[i\]\[j\]\]);
}
if (tmp != maxValue\[i\])
{
noSolution = true;
break;
}
}
// 输出。
if (noSolution)
cout << "NO SOLUTION" << endl;
else
{
// 数字和最大可能值。
int maxSum = ;
for (int i = ; i < MAXCELLS; i++)
maxSum += cells\[i\];
// 数字和最小可能值。最小可能值的含义是取尽可能少的数字，使得满足所有
// 最大值的要求。由于前面的最大可能值方案中已经包含了最小可能值的方案，
// 需要将一些小格置为 0 来获得最小可能值，如果小格置 0 的数目越多，
// 当然最后和更小，那么就要求一个小格的数字尽可能满足多行的最大值要求，
// 这样可以减少非零数字的使用，可以使用动态规划找最小值。
int minSum = dynamic\_programming();
cout << minSum << " " << maxSum << endl;
}
}
return ; }
可怜不知为什么，我的代码竟没能AC。算了，领悟到这样绝妙的思想，已经很满足了。
#include
#include
#include
#include
#include
#define EMPTY (-1)
#define MAXLINES 12 // 行数。
#define MAXCELLS 48 // 小格总个数。
#define MAXLEN (1<<12)
using namespace std;
int lines[MAXLINES][MAXLINES - ] = {
{ , , , , , , , , , , },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , , },
{ , , , , , , , , , , },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , , },
{ , , , , , , , , , , },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , EMPTY, EMPTY },
{ , , , , , , , , , , }
};
string belongs[MAXCELLS] = {
"EL", // 0
"EK", "EL", "FL", // 1 - 3
"AI", "AI", "AJ", "AEJ", "AEK", "AFK", "AFL", "AGL", "AG", "AH", "AH", // 4 - 14
"BI", "BEI", "BEJ", "BFJ", "BFK", "BGK", "BGL", "BHL", "BH", // 15 - 23
"CE", "CEI", "CFI", "CFJ", "CGJ", "CGK", "CHK", "CHL", "CL", // 24 - 32
"DE", "DE", "DF", "DFI", "DGI", "DGJ", "DHJ", "DHK", "DK", "DL", "DL", // 33 - 43
"GI", "HI", "HJ", // 44 - 46
"HI" // 47
};
int maze[];
int maxtype[],tes[];
int sum[MAXLEN],tmp[MAXLEN];
int dp(){
memset(sum,-,sizeof(sum));
sum[]=;
for(int i=;i<;i++){
memcpy(tmp, sum, sizeof(sum));
for(int k=;k<MAXLEN;k++){
if(sum[k]==-)
continue;
for(int p=;lines[i][p]!=EMPTY&&p<MAXLINES-;p++){
// if(maze[lines[i][p]]!=maxtype[i]) continue;
int t=k;
for(int q=;q<belongs[lines[i][p]].length();q++){
if(maze[lines[i][p]]==maxtype[belongs[lines[i][p]][q]-'A'])
t=t|(<<(belongs[lines[i][p]][q]-'A'));
}
if(tmp[t]==-){
tmp[t]=sum[k]+maxtype[i];
}
else {
tmp[t]=min(tmp[t],sum[k]+maxtype[i]);
}
}
}
memcpy(sum, tmp, sizeof(tmp));
// cout<<maxtype[i]<<endl;
}
return sum[MAXLEN-];
}
int main(){
string line;
while (getline(cin, line))
{
// 读入每行的最大值限制。
istringstream iss(line);
for (int i = ; i < MAXLINES; i++)
iss >> maxtype\[i\];
memset(tes,-,sizeof(tes));
for(int i=;i<;i++)
maze\[i\]=;
int ans=;
for(int i=;i<;i++){
for(int k=;k<belongs\[i\].length();k++){
maze\[i\]=min(maze\[i\],maxtype\[belongs\[i\]\[k\]-'A'\]);
}
for(int k=;k<belongs\[i\].length();k++)
tes\[belongs\[i\]\[k\]-'A'\]=max(maze\[i\],tes\[belongs\[i\]\[k\]-'A'\]);
ans+=maze\[i\];
}
bool flag=true;
for(int i=;i<;i++)
if(tes\[i\]!=maxtype\[i\]){
flag=false;
break;
}
if(!flag){
cout<<"NO SOLUTION"<<endl;
continue;
}
int res=dp();
cout<<res<<' '<<ans<<endl;
}
return ; }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章