第一题
来源:P3609 [USACO17JAN] Hoof, Paper, Scissor G
题意
给你n个蹄子/剪刀/布，在你没改变前出法均相同，可以改k次之后最多的相同的局数有多少。
做法
线性DP
因为手势用的字符表示，为方便可以转换为数字
void calc(int i,char a){
if(a=='H'){
d[i]=1;
}else if(a=='P'){
d[i]=2;
}else{
d[i]=3;
}
}
我们还可以写一个check函数，来判断当前出的手势是否可以赢奶牛出的手势
bool check(int x,int y){
if((x==1&&y==2)||(x==2&&y==3)||(x==3&&y==1)){
return true;
}
return false;
}
约定m为题中的k
分析
- 状态定义:f(i,j,k):前i次中改变j次，且第i次手势为k的最大获胜次数
- 状态转移: 不改:f(i,j,k)=f(i-1,j,k)+g
改:f(i,j,k)=max(f(i-1,j,k)+g,f(i-1,j-1,l)+g); 1<=i<=n,1<=j<=m,1<=k,l<=3 g=check(k,s)，s为当前奶牛出的手势 l指除k意外的两种手势
结果: ans=max{f(n,m,l)},l为三种手势
时间复杂度
将字符转为数字为O(n)
dp中:遍历1到n为O(n)
遍历改变情况为O(m)
遍历一遍上一次的手势与当前手势为3*3
check函数为O(1)
时间复杂度约为(9mn)
总时间复杂度约为O(9mn)
代码
这里采用记忆化搜索
#include<iostream>
using namespace std;
int n,m;
const int N=100010;
char s[N];
int d[N];
int f[N][4][110];
void calc(int i,char a){
if(a=='H'){
d[i]=1;
}else if(a=='P'){
d[i]=2;
}else{
d[i]=3;
}
}
bool check(int x,int y){
if((x==1&&y==2)||(x==2&&y==3)||(x==3&&y==1)){
return true;
}
return false;
}
int dfs(int i,int j,int k){
if(f[i][j][k]){
return f[i][j][k];
}
if(i>n){
return 0;
}
int l=check(d[i],j);
int x=dfs(i+1,j,k),y=-0x3f3f3f3f;
if(k>0){
if(j==1){
y=max(dfs(i+1,2,k-1),dfs(i+1,3,k-1));
}else if(j==2){
y=max(dfs(i+1,1,k-1),dfs(i+1,3,k-1));
}else{
y=max(dfs(i+1,1,k-1),dfs(i+1,2,k-1));
}
}
return f[i][j][k]=max(x,y)+l;
}
int main(){
freopen("hps.in","r",stdin);
freopen("hps.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
calc(i,s[i]);
}
int a=dfs(1,1,m);
int b=dfs(1,2,m);
int c=dfs(1,3,m);
cout<<max(a,max(b,c));
}
第二题
来源:P3140 [USACO16FEB] Circular Barn Revisited G
题意:
即求满足给定序列所需要的最小总代价
做法:
考虑线性DP
因为仓库是圆形的，即构成了一个环 所以我们应破环成链
约定m为开门数，即文中给出的k
分析
- 状态定义：f(i,k):开启第i扇门时共开了k扇门的最小总路程
状态计算：f(i,k)=min{f(j-1,k)+g(i,j)};
1<=i<=n,1<=j<=i,1<=k<=m 由于我们破环成链，所以应以1..n为开头依次遍历 l指开头，r指结尾 g(i,j)指由i门转移到j门的路程和
为了节省时间复杂度,g(i,j)可以预处理
结果：ans=min{f(l,m)}; 1<=l<=n;
时间复杂度
瓶颈在dp部分
以1..n为开头依次遍历为O(n)
计算f(i,k)为三重循环，时间复杂度为O(mn^2)
总时间复杂度约为O(mn^3)
注意：不开long long见祖宗
代码
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=210;
int n,m;
int a[N];
int f[N][8],g[N][N];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
a[i+n]=a[i];
}
for(int i=1;i<=2*n;i++){
int x=0;
int d=min(i+n-1,2*n);
for(int j=i+1;j<=d;j++){
x=x+(j-i)*a[j];
g[i][j]=x;
}
}//预处理g数组
int ans=1e18;
for(int l=1;l<=n;l++){//遍历开头
memset(f,0x3f,sizeof f);
f[l-1][0]=0;//初始化f数组
int r=l+n-1;
for(int i=l;i<=r;i++){
for(int j=1;j<=m;j++){
for(int k=l;k<i;k++){
f[i][j]=min(f[i][j],f[k-1][j-1]+g[k][i]);//状态转移
}
}
}
ans=min(ans,f[r][m]);
}
cout<<ans;
}
第三题
来源:P5424 [USACO19OPEN] Snakes G
题意:
将一个长为n的区间分为最多分为 (k+1) 个子区间,每个子区间的代价为 (区间最大值*长度-区间和) ,求最小代价
约定m=k+1
做法:
分段式线性dp
分析
- 状态定义:f(i,j):将前i个数分为j段时，所需要的最小代价
状态转移:f(i,j)=min{f(k-1,j)+(g(k,i)*(i-k+1)-sum(k,i))}
1<=i<=n,1<=j<=i,1<=k<=m 意思是:将前(k-1)个数分为(j-1)段,让k到i为一段 g(k,i)为区间最大值，sum(k,i)为区间和 这两个数组可以预处理
结果:ans=f(n,m)
时间复杂度
预处理 sum() ,g() 可以在O(n^2)的时间中求得
DP部分除计算代价的地方不同以外，其他地方都与分段DP的模板相同
时间复杂度约为O(mn^2)
总时间复杂度约为O(mn^2)
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int N=410;
int f[N][N],d[N][N];
int n,m,a[N];
int sum[N][N];
signed main(){
cin>>n>>m;
m++;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
memset(f,-1,sizeof f);
for(int i=1;i<=n;i++){
int ans=0;
for(int j=i;j<=n;j++){
ans=max(ans,a[j]);
d[i][j]=ans;
sum[i][j]=sum[i][j-1]+a[j];
}
}
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=1;k<=i;k++){
f[i][j]=min(f[i][j],f[k-1][j-1]+(d[k][i]*(i-k+1)-sum[k][i]));
}
}
}
cout<<f[n][m];
}
第四题
来源:UVA11584 Partitioning by Palindromes
题意
当一个字符串正序和反序是完全相同时，我们称之为“回文串”,例如“racecar”就是一个回文串，而“fastcar”就不是
现在给一个字符串s，把它分割成若干个互不相交的回文子串，求分割的回文子串的最少个数
判断是否为回文串可以写一个 check() 函数
bool check(int l,int r){
for(int i=l,j=r;i<=j;i++,j--){
if(s[i]!=s[j]){
return 0;
}
}
return 1;
}
做法:
分段式线性DP
分析:
- 状态定义:f(i):由 1..i 的字符串中，最少可划分为多少个回文串
状态转移:f(i)=min{f(j-1)+1}
1<=i<=n,1<=j<=i 意思为:当满足check(j,i)(即满足 j..i 的字符串为回文串)时,将 1..j-1 的字符串划分为最少回文串数，并加上该串，与f(i)取最小值
结果: ans = f(n)
时间复杂度:
主要是dp部分，时间复杂度为O(n^3)，较高
可以设一个p(i,j),判断由 i..j 的字符串是否为回文串
O(n^2)的时间预处理出所有p(i,j)，并O(n^2)的时间dp
可以自行了解
代码
#include<iostream>
#include<cstring>
using namespace std;
int t;
const int N=1010;
char s[N];
int f[N];
bool check(int l,int r){
for(int i=l,j=r;i<=j;i++,j--){
if(s[i]!=s[j]){
return 0;
}
}
return 1;
}
int main(){
cin>>t;
while(t--){
memset(f,0x3f,sizeof f);
scanf("%s",(s+1));
int x=strlen(s+1);
f[0]=0;
for(int i=1;i<=x;i++){
for(int j=1;j<=i;j++){
if(check(j,i)){
f[i]=min(f[j-1]+1,f[i]);
}
}
}
cout<<f[x]<<endl;
}
}
第五题
来源:UVA11400 Lighting System Design
题意
你的任务是设计一个照明系统，一共有n（n<=1000)种灯泡可供选择,不同种类的灯泡必须用不同的电源，同一种灯泡则可以用一个
输入为一个n，以下n行，每行四个数值，代表电压V，电源费用K，每个灯泡费用C，所需灯泡数量L。n=0为结束标志
做法:
分段式线性dp
首先明确一个性质: 如果当前灯泡不如另外某种的灯泡，那么这类灯泡应全部换成其他比它优的灯泡 否则全部不换
因为只有电压比当前灯泡电压大的灯泡才能将当前灯泡换成该灯泡 所以我们应对灯泡按电压大小排序
分析
- 状态定义:f(i):前i种灯泡在进行操作后的最小总成本
状态转移:f(i)=min{f(j-1)+wb(i)+wc(i)*(sum(i)-sum(j-1))}
1<=i<=n,1<=j<=i 意思是:将 j..i 的灯泡类型全换成第i种，并加上前 j-1 种灯泡在操作后的最小成本，与f(i)取min wc(i)*(sum(i)-sum(j-1)) 指换后的成本 其中:sum指灯泡数量的前缀和
结果: ans = f(n)
时间复杂度
排序为O(nlogn)
预处理前缀和为O(n)
dp套分段dp板子即可,复杂度为O(n^2)
总时间复杂度约为O(n^2)
代码
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
int n;
const int N=1010;
struct node{
int a,b,c,d;
}w[N];
int f[N],sum[N];
bool cmp(node a,node b){
return a.a<b.a;
}
signed main(){
while(cin>>n,n){
memset(f,0x3f,sizeof f);
memset(sum,0,sizeof sum);
for(int i=1;i<=n;i++){
cin>>w[i].a>>w[i].b>>w[i].c>>w[i].d;
}
sort(w+1,w+n+1,cmp);
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+w[i].d;
}
f[0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i]=min(f[i],f[j-1]+w[i].b+w[i].c*(sum[i]-sum[j-1]));
}
}
cout<<f[n]<<endl;
}
}
第六题
来源:P5924 [IOI2004] Phidias 菲迪亚斯神
题意
为了这座雕像他需要大小为 W1*H1,W2*H2...Wn*Hn 的矩形大理石板
最近菲迪亚斯获得一块矩形大理石块。菲迪亚斯想把这块石板切成所需要的大小
石板或是石板所切割出的部分都可以由垂直(或水平)方向纵贯(或是横贯)加以切割到底成为两块矩形石板,同时切割出的这两块矩形石板都必须具有整数的宽度与高度
石板只能以此种方法加以切割，同时石板不能粘合成较大石板
因为石板具有花纹，所以石板也不能旋转
菲迪亚斯想知道如何切割最初的石板，才能让所产生的废料最少
设整个长方形成为W,宽为H
约定a[]为w[],b[]为h[]
做法
记忆化搜索
分析
- 状态定义:dfs(i,j):切割长为i,宽为j的长方形所浪费的最小值
状态转移:dfs(i,j)=min{min(dfs(i,j-b(k))+dfs(i-a[k],b(k)),dfs(i-a(k),j)+dfs(a(k),j-b(k)))}
1<=i<=W,1<=j<=H,1<=k<=n 可知:a(k)<=i,b(k)<=j 其中:dfs(i,j-b(k))+dfs(i-a[k],b(k))为竖着切 dfs(i-a(k),j)+dfs(a(k),j-b(k)))为横着切 因为是记忆化搜索，所以每搜完一个状态就记录它的最小值 f(i,j)初始值(搜索内)为i*j,及最多将整个长方形都浪费，后面挨个挨个取min 注意f要全部初始化为-1(搜索外),因为有可能可以不浪费
结果:ans=dfs(W,H)
时间复杂度
因为记忆化搜索每个状态只会被搜一遍 所以最多搜W*H种状态
总时间复杂度约为O(W*H)
代码
#include<iostream>
#include<cstring>
using namespace std;
int w,h,n;
const int N=1010;
int a[N],b[N];
int f[N][N];
int dfs(int i,int j){
if(f[i][j]!=-1){
return f[i][j];
}
int res=i*j;
for(int k=1;k<=n;k++){
if(a[k]>i||b[k]>j){
continue;
}
int x1=dfs(i,j-b[k])+dfs(i-a[k],b[k]);
int x2=dfs(i-a[k],j)+dfs(a[k],j-b[k]);
int cnt=min(x1,x2);
res=min(res,cnt);
}
return f[i][j]=res;
}
int main(){
memset(f,-1,sizeof f);
cin>>w>>h>>n;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
}
cout<<dfs(w,h);
}
第七题
来源:P4267 [USACO18FEB] Taming the Herd G
题意
农夫想要知道从他开始记录以来发生过多少次出逃。但是，他怀疑奶牛们篡改了它的记录，现在他所确定的只有他是从发生出逃的某一天开始记录的。
请帮助他求出，对于每个从他开始记录以来可能发生的出逃次数，他被篡改了的记录条数的最小值
约定m=n,即可能的出逃最大次数
做法
仍然是分段式线性DP
分析
- 状态定义:f(i,j):前i天中，出逃j次记录的与给定序列不同的最小数目
状态转移:f(i,j)=min{f(k-1,j-1)+g(k,i)}
1<=i<=n,1<=j<=i,1<=k<=i 因为前i天中最多出逃i次，所以j<=i(但设为j<=m也没关系) 意思是:前 (k-1) 天出逃 (j-1) 次(且第k天出逃),一直到第i天再出逃的最小不同数量，与f(i,j)取min 唯一与模板不同的是g(k,i) g(k,i)表示在第k天开始出逃,到第i天时有多少个不同的记录条数 可以预处理得到
结果:ans=f(n,i),1<=i<=n
时间复杂度
预处理g()约为O(n^2) dp约为O(n^3)
总时间复杂度约为O(n^3)
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110;
int n;
int a[N];
int f[N][N];
int g[N][N];
int main(){
memset(f,0x3f,sizeof f);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
g[i][j]=g[i][j-1]+(a[j]!=(j-i));
}
}
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){//n可改为i,降低时间
for(int k=1;k<=i;k++){
f[i][j]=min(f[i][j],f[k-1][j-1]+g[k][i]);
}
}
}
for(int i=1;i<=n;i++){
cout<<f[n][i]<<endl;
}
}
第八题
来源:牛客假日团队赛54-A
题意
在Farmer John最喜欢的节日里，他想要给他的朋友们赠送一些礼物
由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。你可能能够想到，奶牛们本身也不是很擅长包装礼物，而Farmer John即将得到这一教训
Farmer John的N头奶牛（1≤N≤10000）排成一行，方便起见依次编号为1…N。奶牛i的包装礼物的技能水平为si
她们的技能水平可能参差不齐，所以FJ决定把她的奶牛们分成小组。每一组可以包含任意不超过K头的连续的奶牛（1≤K≤1000),并且一头奶牛不能属于多于一个小组
由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平
请帮助FJ求出，在他合理地安排分组的情况下，可以达到的技能水平之和的最大值
做法
还是分段式线性DP
分析
- 状态定义:f(i):前i头牛中,分组后可取到的最高技术和
状态转移:f(i)=min{f(j-1)+w(i,i-j+1)*(i-j+1)}
1<=i<=n,d<=j<=i 其中:d为max(1,i-k+1) 含义就不用多说了 w(i,x)指以i为结尾，取第 i-x+1...i 的最大值 同样预处理
结果:ans=f(n)
时间复杂度
易得:约为O(nm)
代码
#include<iostream>
using namespace std;
const int N=10010;
int f[N];
int n,a[N],k;
int w[N][1010];
int main(){
freopen("teamwork.in","r",stdin);
freopen("teamwork.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
int d=max(1,i-k+1),ans=0;
for(int j=i;j>=d;j--){
ans=max(ans,a[j]);
w[i][i-j+1]=ans;
}
}
for(int i=1;i<=n;i++){
int d=max(1,i-k+1);
for(int j=d;j<=i;j++){
f[i]=max(f[i],f[j-1]+w[i][i-j+1]*(i-j+1));
}
}
cout<<f[n];
}
