本文主要是介绍CCF201809-4 再卖菜(100分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述
试题编号: | 201809-4 |
试题名称: | 再卖菜 |
时间限制: | 1.0s |
内存限制: | 256.0MB |
问题描述: | 问题描述 在一条街上有n个卖菜的商店,按1至n的顺序排成一排,这些商店都卖一种蔬菜。 输入格式 输入的第一行包含一个整数n,表示商店的数量。 输出格式 输出一行,包含n个正整数,依次表示每个商店第一天的菜价。 样例输入 8 样例输出 2 2 2 1 6 5 16 10 数据规模和约定 对于30%的评测用例,2<=n<=5,第二天每个商店的菜价为不超过10的正整数; |
解题思路:差分约束,最长路求解最小值。将边权变为相反值,求最短路,结果的相反数就是要求的最长路。dist[i]表示第一天菜价前i个商店的价格的前缀和。那么就很容易化成 c1<=dist[i]-dist[j]<=c2的形式,然后都标准化为<=的形式,然后求最长路即可。
提交后得100分的C++程序:
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>using namespace std;const int N=310;
const int INF=0x3f3f3f3f;struct Edge{int v,w;Edge(int v,int w):v(v),w(w){}
};vector<Edge>g[N];int dist[N];
bool vis[N];
int a[N];void spfa(int s)
{memset(vis,false,sizeof(vis));fill(dist,dist+N,INF);queue<int>q;q.push(s);vis[s]=true;dist[s]=0;while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(int i=0;i<g[u].size();i++){int v=g[u][i].v;int w=g[u][i].w;if(dist[v]>dist[u]+w) {dist[v]=dist[u]+w;if(!vis[v]){vis[v]=true;q.push(v);}}}}
}int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);//2a1<=s[2]-s[0]<=2a1+1g[0].push_back(Edge(2,-2*a[1]));g[2].push_back(Edge(0,2*a[1]+1));for(int i=2;i<n;i++){//3ai<=s[i+1]-s[i-2]<=3ai+2g[i-2].push_back(Edge(i+1,-3*a[i]));g[i+1].push_back(Edge(i-2,3*a[i]+2));}//2an<=s[n]-s[n-2]<=2an+1g[n-2].push_back(Edge(n,-2*a[n]));g[n].push_back(Edge(n-2,2*a[n]+1));//s[i]-s[i-1]>=1for(int i=1;i<=n;i++)g[i-1].push_back(Edge(i,-1));spfa(0);for(int i=1;i<=n;i++)printf("%d ",-dist[i]-(-dist[i-1]));printf("\n");return 0;
}
这篇关于CCF201809-4 再卖菜(100分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!