POJ3280 Cheapest Palindrome 【DP】
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 6013 | Accepted: 2933 |
Description
Keeping track of all the cows can be a tricky task so Farmer John has installed a system to automate it. He has installed on each cow an electronic ID tag that the system will read as the cows pass by a scanner. Each ID tag's contents are currently a single
string with length M (1 ≤ M ≤ 2,000) characters drawn from an alphabet of N (1 ≤ N ≤ 26) different symbols (namely, the lower-case roman alphabet).
Cows, being the mischievous creatures they are, sometimes try to spoof the system by walking backwards. While a cow whose ID is "abcba" would read the same no matter which direction the she walks, a cow with the ID "abcb" can potentially register as two
different IDs ("abcb" and "bcba").
FJ would like to change the cows's ID tags so they read the same no matter which direction the cow walks by. For example, "abcb" can be changed by adding "a" at the end to form "abcba" so that the ID is palindromic (reads the same forwards and backwards).
Some other ways to change the ID to be palindromic are include adding the three letters "bcb" to the begining to yield the ID "bcbabcb" or removing the letter "a" to yield the ID "bcb". One can add or remove characters at any location in the string yielding
a string longer or shorter than the original string.
Unfortunately as the ID tags are electronic, each character insertion or deletion has a cost (0 ≤ cost ≤ 10,000) which varies depending on exactly which character value to be added or deleted. Given the content of a cow's ID tag and the cost of
inserting or deleting each of the alphabet's characters, find the minimum cost to change the ID tag so it satisfies FJ's requirements. An empty ID tag is considered to satisfy the requirements of reading the same forward and backward. Only letters with associated
costs can be added to a string.
Input
Line 2: This line contains exactly M characters which constitute the initial ID string
Lines 3..N+2: Each line contains three space-separated entities: a character of the input alphabet and two integers which are respectively the cost of adding and deleting that character.
Output
Sample Input
3 4
abcb
a 1000 1100
b 350 700
c 200 800
Sample Output
900
Hint
Source
dp[i][j]表示从字符串的位置i到位置j转换成回文串所须要的最小费用,当str[i]==str[j]时,dp[i][j]=dp[i+1][j-1];否则dp[i][j]=min(dp[i+1][j]+cost[i], dp[i][j-1]+cost[j]);
#include <stdio.h>
#include <string.h> #define maxn 2010 char str[maxn];
int dp[maxn][maxn];
struct Node {
int add, del;
} cost[26]; int min(int a, int b) {
return a < b ? a : b;
} int getDele(char ch) {
return cost[ch - 'a'].del;
} int getAdd(char ch) {
return cost[ch - 'a'].add;
} int main() {
// freopen("stdin.txt", "r", stdin);
int N, M, i, j, id, step, len;
char buf[2];
scanf("%d%d", &N, &M);
scanf("%s", str);
memset(cost, -1, sizeof(cost));
while(M--) {
scanf("%s", buf);
id = buf[0] - 'a';
scanf("%d%d", &cost[id].add, &cost[id].del);
}
len = strlen(str);
for(step = 1; step < len; ++step)
for(i = 0; i + step < len; ++i) {
if(str[i] == str[i+step])
dp[i][i+step] = dp[i+1][i+step-1];
else {
dp[i][i+step] = min(min(dp[i+1][i+step] + getDele(str[i]), dp[i][i+step-1] + getDele(str[i+step])), min(dp[i+1][i+step] + getAdd(str[i]), dp[i][i+step-1] + getAdd(str[i+step])));
}
}
printf("%d\n", dp[0][len-1]);
return 0;
}
版权声明:本文博主原创文章。博客,未经同意不得转载。
最新文章
- 记2016腾讯 TST 校招面试经历,电面、笔试写代码、技术面、hr面,共5轮
- 撤销git reset soft head操作
- Java 集合系列18之 Iterator和Enumeration比较
- Linux内核分析——操作系统是如何工作的
- android 学习随笔十八(广播与服务 )
- php接口开发--复制缩减Codeigniter的车轮
- Linux中下载,压缩,解压等命令
- python 魔法方法(学习过程的笔记)
- 2.4 PCI总线的配置
- Lesson 27 A wet night
- [Swift]LeetCode268. 缺失数字 | Missing Number
- 一条shell命令让多台Linux服务器执行
- ie11~ie9兼容的布局写法。bootsteap的12栅格,栅格化就可以实现。
- 找回Android studio的帮助文档
- android 面试准备基础题
- 【BZOJ4822】[CQOI2017]老C的任务(扫描线)
- Python 学习书籍推荐
- tomcat下程序包的安装与部署
- [Python] numpy.Matrix
- Visio2013 64位下载安装以及破解激活教程
热门文章
- 【Codeforces Round #443 (Div. 2) C】Short Program
- &;lt;九度 OJ&;gt;题目1012:畅通project
- JAVA初始开发环境搭建
- 【a101】高精度实数加法
- 【35.37%】【codeforces 556C】Case of Matryoshkas
- WordPress的后台功能菜单介绍与操作,WordPress后台说明
- ios开发核心动画七:核心动画与UIView动画的区别
- php实现 统计每个月兔子的数量
- USB 3.0规范中译本 第10章 集线器,主机下行口以及设备上行口规范
- php实现数组中的逆序对(归并排序实现:排序 辅助数组)