动态规划
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int N=11,M=28,inf=0x3f3f3f,Day=30;
int dp[32][N+1][405][605],zd,qd,FZ;
int cost_water,cost_food,walk,dig,buy;
int xh_water[3]= {5,8,10},xh_food[3]= {7,6,10};//不同天气条件基础消耗
bool cz[N+1],ks[N+1];
struct node
{
short day; // 天数
short from; // 持续天数
int water,food;
int money;
bool operator!=(const node &x)
{
return x.day!=day || x.from!=from || x.water!=water || x.food!=food ;
};
} path[31][N+1][405][605],lastpath;
int weather[31]=
{-1,1,1,0,2,0,1,2,0,1,1,
2,1,0,1,1,1,2,2,1,1,
0,0,1,0,2,1,0,0,1,1
};//30天的天气条件情况“1”代表高温，“0”代表晴朗，“2”代表沙暴
vector <int> g[N];
map <int,int> mp;
void push_back(int x,int y)
{
g[x].push_back(y);
g[y].push_back(x);
}
void build_map()
{
push_back(1,2);//从哪走到哪
push_back(2,3);
push_back(2,5);
push_back(5,6);
push_back(3,4);
push_back(4,7);
push_back(6,7);
push_back(7,8);
push_back(8,9);
push_back(9,10);
push_back(10,11);
mp[1]=1;//走哪
mp[2]=25;
mp[3]=26;
mp[4]=27;
mp[5]=24;
mp[6]=23;
mp[7]=21;
mp[8]=9;
mp[9]=15;
mp[10]=14;
mp[11]=12;
for(int i=1; i<=N; i++)
{
cz[i]=0;
ks[i]=0;
}
cz[9]=1;
ks[11]=1;
zd=4;
qd=1;
return ;
}
void init()
{
memset(dp,-inf,sizeof(dp));
FZ=1200;
cost_water=5;
cost_food=10;
walk=2;
buy=2;
dig=3;
for(int k=0; k<=405; k++)
{
for(int l=0; l<=601; l++)
{
if(k*3+l*2<=FZ)
{
dp[0][qd][k][l]=10000-k*cost_water-l*cost_food;
}
}
}
printf("init %d\n",dp[0][1][178][333]);
path[0][1][0][0]= {0,0,0,0};
return ;
}
int main()
{
build_map();
init();
for(int i=0; i<Day; i++)
{
printf("第%d天\n",i);
int tq=weather[i];
for(int j=1; j<=N; j++)
{
if(cz[j])// 村庄
{
for(int w=0; w<=405; w++)
{
for(int f=0; w*3+f*2<=1200; f++)
{
//购买或不够买物资(ww=0,ff=0就是不购买)
if(tq==2) //停留
{
int money=dp[i][j][w][f];
for(int ww=0; ww<=money/cost_water; ww++)
{
for(int ff=0; ff<=(FZ-(w+ww)*3)/2-f; ff++)
{
if(w+ww-xh_water[tq]>=0&&f+ff-xh_food[tq]>=0&&dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food>=0)
{
if(dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]<dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food)
{
dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]=dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food;
path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]= {i,j,w,f,dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food};
}
}
}
}
}
else //从j走到jj
{
for(auto jj :g[j])
{
int money=dp[i][j][w][f];
for(int ww=0; ww<=money/cost_water; ww++)
{
for(int ff=0; ff<=(FZ-(w+ww)*3)/2-f; ff++)
{
if(w+ww-walk*xh_water[tq]>=0&&f+ff-walk*xh_food[tq]>=0&&dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food>=0)
{
if(dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]<dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food)
{
dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]=dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food;
path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]= {i,j,w,f,dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food};
}
}
}
}
}
}
}
}
}
else if (ks[j])// 矿山
{
for(int w=0; w<=405; w++)
{
for(int f=0; w*3+f*2<=1200; f++)
{
// 已经停留一天了，可以挖矿
if(w-dig*xh_water[tq]>=0&&f-dig*xh_food[tq]>=0)
{
if(dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]<dp[i][j][w][f]+1000&&dp[i][j][w][f]>=0)
{
dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]=dp[i][j][w][f]+1000;
path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]= {i,j,w,f,dp[i][j][w][f]+1000};
}
}
// 在矿山不挖矿或 不允许挖矿
if(tq==2) //停留但不挖矿
{
if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0)
{
if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0)
{
dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];
path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]= {i,j,w,f,dp[i][j][w][f]};
}
}
}
else
{
if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0)
{
for(auto jj:g[j])
{
if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0)
{
dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];
path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]= {i,j,w,f,dp[i][j][w][f]};
}
}
}
}
}
}
}
else //普通区
{
for(int w=0; w<=405; w++)
{
for(int f=0; w*3+f*2<=1200; f++)
{
if(tq==2) //在j点停留
{
if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0&&dp[i][j][w][f]>=0)
{
if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f])
{
dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];
path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]= {i,j,w,f,dp[i][j][w][f]};
}
}
}
else// 走到jj点
{
for(auto jj :g[j])
{
if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0&&dp[i][j][w][f]>=0)
{
if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f])
{
dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];
path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]= {i,j,w,f,dp[i][j][w][f]};
}
}
}
}
}
}
}
}
}
int ans=-inf;
node lastpath;
int last_water=0,last_food=0,last_day=Day;
for(int i=0; i<=Day; i++)
{
for(int w=0; w<=405; w++)
for(int f=0; w*3+2*f<=1200; f++)
{
if(dp[i][zd][w][f]>ans)
{
ans=dp[i][zd][w][f];
lastpath=path[i][zd][w][f];
last_water=w;
last_food=f;
last_day=i;
}
}
}
stack<node> s;
stack<int> my;
printf("天数:%d 天气:%d %d 水:%d 食物:%d 资金:%d\n",last_day,weather[Day],zd,last_water,last_food,ans);
s.push((node)
{
last_day,zd,last_water,last_food,ans
});
while(lastpath!=path[0][1][0][0])
{
s.push(lastpath);
printf("天数:%d 天气:%d %d 天气:%d 食物:%d 资金:%d\n",lastpath.day,weather[lastpath.day],mp[lastpath.from],lastpath.water,lastpath.food,lastpath.money);
my.push(lastpath.money);
lastpath=path[lastpath.day][lastpath.from][lastpath.water][lastpath.food];
}
freopen("output.txt","w",stdout);
my.push(my.top());
while (!s.empty())
{
node t=s.top();
int money=my.top();
printf("天数:%d 天气:%d 获得资金:%d 水:%d 食物:%d 资金:%d\n",t.day,weather[t.day],mp[t.from],t.water,t.food,money);
s.pop();
my.pop();
}
printf("%d\n",ans);
return 0;
}
运行结果及报错内容
D:\Users\86187\Documents\shuame\Cache\穿越沙漠\main.cpp|140|error: 'jj' does not name a type|
D:\Users\86187\Documents\shuame\Cache\穿越沙漠\main.cpp|159|error: expected ';' before '}' token|
D:\Users\86187\Documents\shuame\Cache\穿越沙漠\main.cpp|159|error: expected primary-expression before '}' token|
D:\Users\86187\Documents\shuame\Cache\穿越沙漠\main.cpp|159|error: expected ';' before '}' token|
D:\Users\86187\Documents\shuame\Cache\穿越沙漠\main.cpp|159|error: expected primary-expression before '}' token|
D:\Users\86187\Documents\shuame\Cache\穿越沙漠\main.cpp|159|error: expected ')' before '}' token|
D:\Users\86187\Documents\shuame\Cache\穿越沙漠\main.cpp|159|error: expected primary-expression before '}' token|
D:\Users\86187\Documents\shuame\Cache\穿越沙漠\main.cpp|159|error: expected ';' before '}' token|
D:\Users\86187\Documents\shuame\Cache\穿越沙漠\main.cpp|175|warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]|
