IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> 例题 9-23 有趣的游戏(Fun Game,ACM/ICPC Beijing 2004,UVa1204) -> 正文阅读

[C++知识库]例题 9-23 有趣的游戏(Fun Game,ACM/ICPC Beijing 2004,UVa1204)

原题链接:https://vjudge.net/problem/UVA-1204
分类:状压DP
备注:字符串覆盖

按紫书的思路,首先排除被覆盖的串,每个串都试着正反两个状态,与当前集合的最后一个串计算覆盖量,取最优。这里固定以某一个串为第一个串,就可以很方便地来把最后一个串和第一个串连起来。

注意有效串个数为1,以及长度小于等于1应该变为2的情况。

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
const int INF = 0x3f3f3f3f;

int n, len[N], cover[N][N][2][2], dp[1 << N][N][2];
// dp[s][i][o],其中s表示已经加入的字符串的集合,i表示结尾串的编号,o表示结尾串是正向还是逆向 
string s[N][2];

struct String {
	string s, rev;
	bool operator < (const String& rhs) const {
		return s.length() < rhs.s.length();
	}
}input[N];

int calc(const string& a, const string& b) {
	int len1 = a.length();
	int len2 = b.length();
	for (int i = 1; i < len1; i++) {
		if (i + len2 < len1) continue;
		int flg = 1;
		for (int j = 0; i + j < len1; j++) {
			if (a[i + j] != b[j]) {
				flg = 0;
				break;
			}
		}
		if (flg) return len1 - i;
	}
	return 0;
}

int main(void) {
//	freopen("in.txt", "r", stdin); 
//	freopen("out.txt", "w", stdout);
	while(cin >> n && n) {
		for (int i = 0; i < n; i++) {
			cin >> input[i].s;
			input[i].rev = input[i].s;
			reverse(input[i].rev.begin(), input[i].rev.end());
		}
		sort(input, input + n);
		int tot = 0, sumLen = 0;
		for (int i = 0; i < n; i++) {
			int covered = 0;
			for (int j = i + 1; j < n; j++) {
				if (input[j].s.find(input[i].s) != string::npos ||
				    input[j].s.find(input[i].rev) != string::npos) {
					covered = 1;
					break;    	
				}
			}
			if (covered) continue;
			s[tot][0] = input[i].s;
			s[tot][1] = input[i].rev;
			len[tot] = input[i].s.length();
			sumLen += len[tot];
			tot++;
		}
		for (int i = 0; i < tot; i++)
			for (int j = 0; j < tot; j++)
				for (int o1 = 0; o1 < 2; o1++) 
					for (int o2 = 0; o2 < 2; o2++) 
						cover[i][j][o1][o2] = calc(s[i][o1], s[j][o2]);
		memset(dp, -1, sizeof(dp));
		// 固定将第一个字符串正向摆放 
		dp[1][0][0] = 0;
		for (int sta = 1; sta < (1 << tot) - 1; sta++) 
			for (int e = 0; e < tot; e++) // 当前尾部串编号为e 
				for (int o = 0; o < 2; o++)
					if (dp[sta][e][o] >= 0)
						for (int j = 1; j < n; j++) {
							if (sta & (1 << j)) continue;
							for (int o2 = 0; o2 < 2; o2++)
								dp[sta | (1 << j)][j][o2] = max(dp[sta | (1 << j)][j][o2], dp[sta][e][o] + cover[e][j][o][o2]);
						}
		int maxCover = 0, ans;
		for (int i = 1; i < tot; i++)
			for (int o = 0; o < 2; o++)
				maxCover = max(maxCover, dp[(1 << tot) - 1][i][o] + cover[i][0][o][0]);
		if (tot == 1) ans = len[0] - cover[0][0][0][0];
		else ans = sumLen - maxCover;
		cout << (ans <= 1 ? 2 : ans) << endl;
	}
	return 0;
} 
  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现(C语言)
C++PrimerPlus 第七章 函数-C++的编程模块(
Problem C: 算法9-9~9-12:平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇(六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2021-09-24 10:21:37  更:2021-09-24 10:23:53 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/23 23:24:30-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码