【DP】洛谷P1070 道路游戏O(n^3)
程序员文章站
2022-06-25 16:15:59
-Problem Link-emmmmm这里n^3卡过去了,后续会上传新的优化后的打法题目Sample-in2 3 2 1 2 3 2 3 4 1 2Sample-out5思路DP,很容易想到设一个f[t]=t的时间内所能得到的最大金币转移为:f[t]=max(f[t-j]+money-price)代码这个是没卡过的96分,便于放注释就放上来了,卡过100分的请往下拉拉。#include#include#in...
-Problem Link-
emmmmm这里n^3卡过去了
题目
Sample-in
2 3 2
1 2 3
2 3 4
1 2
Sample-out
5
思路
DP,很容易想到设一个f[t]=t的时间内所能得到的最大金币
转移为:f[t]=max(f[t-j]+money-price)
代码
这个是没卡过的96分,便于放注释就放上来了,卡过100分的请往下拉拉。
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n,m,p,w,w1,price[1001],money[1001][1001],f[1001];
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
scanf("%d",&money[i][j]);
for(int j = 1; j <= m; ++j) //前缀和处理一下
for(int i = 1; i <= n; ++i){
if(i==1) money[i][j] += money[n][j-1];
else money[i][j] += money[i-1][j-1];
}
for(int i = 1; i <= n; ++i)
scanf("%d",&price[i]);
for(int t = 1; t <= m; ++t){ //时间轴
f[t] = -100000000; //初始化,因为结果可能为负数
for(int i = 1; i <= n; ++i){ //从这个点买个机器人
w = i-1; if(w==0) w = n; //前缀和用
for(int j = 1; j <= min(p,t); ++j){ //机器人走的步数
w1 = i+(j%n)-1; if(w1>n) w1-=n; if(w1==0) w1=n; //最终走到的点
f[t] = max(f[t], f[t-j]+money[w1][t]-money[w][t-j]-price[i]); //如上所述
//之前取到过的+路上的金币+机器人价格
}
}
}
printf("%d ",f[m]); //输出
}
100分的。
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n,m,p,w,w1,k,pt,price[1001],money[1001][1001],f[1001];
int read(){
int xx=0; char c;
c = getchar();
while(c>'9'||c<'0') c = getchar();
while(c<='9'&&c>='0'){
xx = xx*10+c-48;
c = getchar();
}
return xx;
}
int main(){
n=read();
m=read();
p=read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
money[i][j]=read();
for(int j = 1; j <= m; ++j)
for(int i = 1; i <= n; ++i){
if(i==1) money[i][j] += money[n][j-1];
else money[i][j] += money[i-1][j-1];
}
for(int i = 1; i <= n; ++i)
price[i]=read();
for(int t = 1; t <= m; ++t){
pt = min(p,t);
f[t] = -1000000000;
for(int i = 1; i <= n; ++i){
w = i-1;
w = w==0?n:w;
for(int j = 1; j <= pt; ++j){
w1 = (i+j-1)%n;
w1 = w1==0?n:w1;
k=f[t-j]+money[w1][t]-money[w][t-j]-price[i];
f[t] = f[t]<k?k:f[t];
}
}
}
printf("%d ",f[m]);
}
本文地址:https://blog.csdn.net/qq_42937087/article/details/107852188
上一篇: 917代表的爱情数字含义是什么(全网最全的爱情数字及含义)
下一篇: 元旦吃汤圆吗