// Problem: CF1110E Magic Stones // Contest: Luogu // URL: https://www.luogu.com.cn/problem/CF1110E // Memory Limit: 250 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h> usingnamespace std; #define int long long inlineintread(){int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+ (x<<3)+(ch^48);ch=getchar();}return x*f;} //#define M //#define mo #define N 200010 int n, m, i, j, k; int a[N]; map<int, int>mp;
// Problem: 棋盘分割 // Contest: POJ - Noi 99 // URL: http://poj.org/problem?id=1191 // Memory Limit: 10 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)
// #include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> usingnamespace std; #define int long long inlineintread(){int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+ (x<<3)+(ch^48);ch=getchar();}return x*f;} //#define M //#define mo #define N 10 int n, m, i, j, k; int f[N][N][N][N][16]; int s[N][N], a[N][N], sigam[N][N][N][N]; double he;
intsum(int lx, int ly, int rx, int ry) { if(sigam[lx][ly][rx][ry]!=-1) return sigam[lx][ly][rx][ry]; int Sum=s[rx][ry]-s[lx-1][ry]-s[rx][ly-1]+s[lx-1][ly-1]; return sigam[lx][ly][rx][ry]=Sum*Sum; }
intdfs(int lx, int ly, int rx, int ry, int k) { if(f[lx][ly][rx][ry][k]!=-1) return f[lx][ly][rx][ry][k]; if(k==1) return f[lx][ly][rx][ry][k]=sum(lx, ly, rx, ry); int ans=999999999999; for(int i=lx; i<rx; ++i) { ans=min(ans, dfs(lx, ly, i, ry, k-1)+sum(i+1, ly, rx, ry)); ans=min(ans, sum(lx, ly, i, ry)+dfs(i+1, ly, rx, ry, k-1)); } for(int i=ly; i<ry; ++i) { ans=min(ans, dfs(lx, ly, rx, i, k-1)+sum(lx, i+1, rx, ry)); ans=min(ans, sum(lx, ly, rx, i)+dfs(lx, i+1, rx, ry, k-1)); } return f[lx][ly][rx][ry][k]=ans; }
Define the distance between two strings of the same length as the numbers of the positions where the characters differ in these two strings.
If two strings of the same length has a distance of no more than k, we call these two string satisfy k−matching.
Given a string S of length n and a integer k. For each i∈[1,n−1], split S into substrings A and B, while A=S[1,i] and B=S[i+1,n]. For all the string pairs formed by some non empty substring of A and some non empty substrings of B, count the numbers of pairs satisfying k−matching.
给定一个串 S，对于每一个前缀 A 以及对应的后缀 B，问有多少个子串对之间的距离不超过 K。
两个相同长度的串的距离定义为他们不同字符的个数。
#include<bits/stdc++.h> usingnamespace std; #define int long long inlineintread(){int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+ (x<<3)+(ch^48);ch=getchar();}return x*f;} //#define M //#define mo #define N 3010 int n, m, i, j, k; int c[N], cha[N], ans[N]; int f, t, l, len, dif; char s[N];
Your company has just constructed a new skyscraper, but you just noticed a terrible problem: there is only space to put one game room on each floor! The game rooms have not been furnished yet, so you can still decide which ones should be for table tennis and which ones should be for pool. There must be at least one game room of each type in the building.
Luckily, you know who will work where in this building (everyone has picked out offices). You know that there will be Ti table tennis players and Pi pool players on each floor. Our goal is to minimize the sum of distances for each employee to their nearest game room. The distance is the difference in floor numbers: 0 if an employee is on the same floor as a game room of their desired type, 1 if the nearest game room of the desired type is exactly one floor above or below the employee, and so on.
计划建设 N 层高的运动楼，每层楼要么建游泳池，要么建乒乓球室，只能二选一。
已知第 i 层有 Ti 个人打乒乓球，Pi 个人想游泳。
如果该层楼没有对应的功能室，对应的人只能去最近的楼层运动。
单个人爬一层楼的额外运动量是 1，问最合理的设计下，满足每个人的需求时，最少付出的额外运动量总和是多少。
N<=4000,0<=Ti,Pi<=109
思路
设 dp(i,k) 表示第 i 层修建设施 k，且第 i+1 层修建另一种建筑物，前 i 层的最小代价。
#include<bits/stdc++.h> usingnamespace std; #define int long long inlineintread(){int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+ (x<<3)+(ch^48);ch=getchar();}return x*f;} //#define M //#define mo #define N 4010 int n, m, i, j, k; int sum[N][2], dsm[N][2], dp[N][2]; int l, r, mid, x, ans, t, T;
intgoup(int l, int r, int k)// [l, r]-> r+1 { return (sum[r][k]-sum[l-1][k])*(r+1)-(dsm[r][k]-dsm[l-1][k]); }
intgodown(int l, int r, int k)// [l, r]->l-1 { return (dsm[r][k]-dsm[l-1][k])-(sum[r][k]-sum[l-1][k])*(l-1); }
intgo(int l, int r, int k) { mid=(l+r)>>1; returngodown(l, mid, k)+goup(mid+1, r, k); }
There is a n×m board, a chess want to go to the position
(n,m) from the position (1,1).
The chess is able to go to position (x2,y2) from the position (x1,y1), only and if only x1,y1,x2,y2 is satisfied that (x2−x1)2+(y2−y1)2=5, x2>x1, y2>y1.
Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle.
I want you to tell me, There are how may ways the chess can achieve its goal.
#include<bits/stdc++.h> usingnamespace std; #define int long long inlineintread(){int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+ (x<<3)+(ch^48);ch=getchar();}return x*f;} //#define M #define p 110119 #define NN 120 structnode { int x, y; }a[NN]; int n, m, i, j, k; int jc[p*3], dp[NN]; int f, ans, N, M, t;
Bubu’s bookshelf is in a mess! Help him!
There are nbooks on his bookshelf. We define the mess value to be the number of segments of
consecutive equal-height books. For example, if the book heights are 30, 30, 31, 31, 32, the mess
value is 3, that of 30, 32, 32, 31 is also 3, but the mess value of 31, 32, 31, 32, 31 is 5 — it’s indeed in
a mess!
Bubu wants to reduce the mess value as much as possible, but he’s a little bit tired, so he decided
to take out at most kbooks, then put them back somewhere in the shelf. Could you help him?
书架上有 N 本书，书本高度是 [25cm，32cm]，凌乱地排着。
定义一排书的整齐度是指最少可以被划分成高度连续相等的书的段数。
比如 {30，32，32，31} 整齐度是 3。
比如 {31，32，31，32，31} 整齐度是 5。
现在最多从其中拿出 K 本书，然后塞回去。
问整理后，最少可以有多少段高度相等的连续区间。
K <= N <= 100
思路
发现书本高度最大最小差为8，很容易想到状压dp。
设 dp(i,j,k,o) 表示前 i 本书里拿出 j 本，剩下书高度集合为 k，且最后一本书高度为 o 的最小凌乱度。
然后枚举每一本书拿或者不拿。
如果不拿，则 k 变成 k∣(1<<ai)，代表这本书放入未被拿的集合。o 变成 ai。如果之前 o=ai，则要加1。
// Problem: UVA12235 Help Bubu // Contest: Luogu // URL: https://www.luogu.com.cn/problem/UVA12235 // Memory Limit: 0 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h> usingnamespace std; //#define int long long inlineintread(){int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+ (x<<3)+(ch^48);ch=getchar();}return x*f;} //#define M //#define mo #define N 110 int n, m, i, j, k; int ans, dp[2][N][300][10]; int is[1010][10], a[1010]; int o, nw, ls, K, t;
