UVaLive 4256 Salesmen (简单DP)
2024-08-29 11:28:42
题意:给一个无向连通图,和一个序列,修改尽量少的数,使得相邻两个数要么相等,要么相邻。
析:dp[i][j] 表示第 i 个数改成 j 时满足条件。然后就很容易了。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define debug() puts("++++");
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std; typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 100 + 5;
const int mod = 2000;
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, 1, -1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
int dp[maxn<<1][maxn];
bool G[maxn][maxn];
int a[maxn<<1]; int main(){
int T; cin >> T;
while(T--){
int t;
scanf("%d %d", &n, &m);
memset(G, false, sizeof G);
for(int i = 0; i < m; ++i){
int u, v;
scanf("%d %d", &u, &v);
G[u][v] = G[v][u] = true;
}
scanf("%d", &t);
for(int i = 0; i < t; ++i) scanf("%d", a+i);
memset(dp, INF, sizeof dp);
for(int i = 1; i <= n; ++i) dp[0][i] = a[0] == i ? 0 : 1;
for(int i = 1; i < t; ++i)
for(int j = 1; j <= n; ++j){
dp[i][j] = a[i] == j ? dp[i-1][j] : dp[i-1][j] + 1;
for(int k = 1; k <= n; ++k)
if(G[j][k]) dp[i][j] = min(dp[i][j], a[i] == j ? dp[i-1][k] : dp[i-1][k] + 1);
} int ans = INF;
for(int i = 1; i <= n; ++i) ans = min(ans, dp[t-1][i]);
printf("%d\n", ans);
}
return 0;
}
最新文章
- android:布局、绘制、内存泄露、响应速度、listview和bitmap、线程优化以及一些优化的建议!
- java 截取pdf
- 【转】Reactor与Proactor两种模式区别
- Android Studio 生成Release版,报Warning的解决办法
- WPS for ubuntu14
- Macbook之用brew安装Python
- libvlc 双击,鼠标事件消息响应
- HID Keyboard &; Mouse descriptor.
- springMVC框架中json处理
- ucos调度器详解
- 【转】进程间通信方式总结(windows 和linux)
- javaApplication中如何使用log4j
- centos6.5中部署Zeppelin并配置账号密码验证
- 登录之md5加密
- 【转载】为什么任何随便输入的账号使用SYSDBA权限都能登陆oracle
- iOS连续上传多张图片
- CUDA C Programming Guide 在线教程学习笔记 Part 9
- CSS3盒子模型(中)
- golang管道
- [bzoj3995] [SDOI2015]道路修建 线段树
热门文章
- ZOJ 3502	 Contest <;状态压缩 概率 DP>;
- 常用脚本--查看死锁和阻塞usp_who_lock(转)
- SQLServer中游标实例介绍(转)
- 九度OJ 1078:二叉树遍历 (二叉树)
- 【题解】P3258松鼠的新家
- Spring/Java error: namespace element &#39;annotation-config&#39; … on JDK 1.5 and higher
- 畅游HttpCore
- EASYARM-IMX283 nfs启动内核和根文件系统
- Centos7 安装lnmp
- Linux_服务器_02_在linux上怎么看eclipse控制台输出语句