鋪設道路road.cpp時空限制1000ms / 128MB（貪心）
題目描述
春春是一名道路工程師，負責鋪設一條長度為 n 的道路。
鋪設道路的主要工作是填平下陷的地表。整段道路可以看作是 n 塊首尾相連的區域，一開始，第 ii 塊區域下陷的深度為di 。
春春每天可以選擇一段連續區間[L,R] ，填充這段區間中的每塊區域，讓其下陷深度減少 1。在選擇區間時，需要保證，區間内的每塊區域在填充前下陷深度均不為 0 。
春春希望你能幫他設計一種方案，可以在最短的時間内将整段道路的下陷深度都變為 0 。
輸入輸出格式
輸入格式：road.in
輸入檔案包含兩行，第一行包含一個整數 n，表示道路的長度。 第二行包含 n 個整數，相鄰兩數間用一個空格隔開，第i 個整數為 di 。
輸出格式：road.out
輸出檔案僅包含一個整數，即最少需要多少天才能完成任務。
輸入輸出樣例
輸入樣例：
6
4 3 2 5 3 5
輸出樣例#1：
9
說明
【樣例解釋】
一種可行的最佳方案是，依次選擇： [1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。
【資料規模與約定】
對于 30% 的資料，1≤n≤10 ；
對于 70% 的資料，1≤n≤1000 ；
對于 100% 的資料，1≤n≤100000,0≤di≤10000 。
【思路】：
首先要考慮一個問題，填深坑時會把淺的也一起填起來，是以隻要用深的減去淺的，求和就是答案
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int n,a[1000080];
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
a[i]=read();
}
int ans=a[1];
for(int i=2;i<=n;++i)
{
if(a[i]>a[i-1])
ans+=(a[i]-a[i-1]);
}
cout<<ans;
return 0;
} 2、貨币系統（money.cpp）時空限制1000ms / 128MB
題目描述
在網友的國度中共有 n 種不同面額的貨币，第 i 種貨币的面額為 a[i]，你可以假設每一種貨币都有無窮多張。為了友善，我們把貨币種數為 n、面額數組為 a[1..n] 的貨币系統記作 (n,a)。
在一個完善的貨币系統中，每一個非負整數的金額 x 都應該可以被表示出，即對每一個非負整數 x，都存在 n 個非負整數 t[i] 滿足 a[i]×t[i] 的和為 x。然而， 在網友的國度中，貨币系統可能是不完善的，即可能存在金額 x不能被該貨币系統表示出。例如在貨币系統 n=3, a=[2,5,9] 中，金額 1,3 就無法被表示出來。
兩個貨币系統 (n,a) 和 (m,b) 是等價的，當且僅當對于任意非負整數 x，它要麼均可以被兩個貨币系統表出，要麼不能被其中任何一個表出。
現在網友們打算簡化一下貨币系統。他們希望找到一個貨币系統 (m,b)，滿足 (m,b) 與原來的貨币系統 (n,a)等價，且 m 盡可能的小。他們希望你來協助完成這個艱巨的任務：找到最小的 m。()
輸入格式：money.in
輸入檔案的第一行包含一個整數 T，表示資料的組數。
接下來按照如下格式分别給出 T 組資料。 每組資料的第一行包含一個正整數 n。接下來一行包含 n 個由空格隔開的正整數 a[i]。
輸出格式：money.out
輸出檔案共有 T 行，對于每組資料，輸出一行一個正整數，表示所有與 (n,a) 等價的貨币系統 (m,b) 中，最小的 m。
輸入輸出樣例
輸入樣例#1：
2
4
3 19 10 6
5
11 29 13 19 17
輸出樣例#1：
2
5
說明
在第一組資料中，貨币系統 (2, [3,10]) 和給出的貨币系統 (n, a) 等價，并可以驗證不存在 m < 2的等價的貨币系統，是以答案為 2。 在第二組資料中，可以驗證不存在 m < n的等價的貨币系統，是以答案為 5。
【資料範圍與約定】
【思路】：
其實這破題我一開始就沒讀懂（霧？）後來研究了一下樣例發現6不合法的原因是因為6=3+3=3*3，而19=10+6+3是以把它們删去
樣例2中沒有任意一個數會被其他的數的積或者和表示是以答案是5（嘿嘿）
解法一：
求完全背包完全背包的方案數，可以把要表示的大面額看成背包容量，把小面額看成單個物品的重量就成了完全背包。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
/*完全背包*/
const int N=255555;
int all_beibao[N],f[N],n,by,js;
void start() {
memset(f,0,sizeof(f));
memset(all_beibao,0,sizeof(all_beibao));
js=0 ;
}
int main () {
scanf("%d",&by);
while(by--) {
start();
n=read();
for(int i=1; i<=n; ++i) {
f[i]=read();
}
sort(f+1,f+1+n);
all_beibao[0]=1 ;
for(int i=1; i<=n; ++i) {
if(!all_beibao[f[i]]) {
js++;
}
for(int j=f[i]; j<=f[n]; ++j) {
all_beibao[j]+=all_beibao[j-f[i]];
}
}
printf("%d\n",js);
}
return 0 ;
} 解法二：
竟然小數可以表示出大數，我們的目的是要把大數先删掉那就可以從小到大排序後把小數能表示的數求出來然後删掉（其實這才是我真正的思路，隻不過比較傻）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int n,t,a[25555],visit[25555],ans;
int main() {
cin>>t;
while(t--) {
ans=0;
cin>>n;
memset(visit,0,sizeof(visit));
for(int i=1; i<=n; ++i) {
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1; i<=n; ++i) {
if(!visit[a[i]])
ans++;
for(int j=1; j<=a[n]; ++j) {
if(j*a[i]<=a[n]) {
visit[j*a[i]]=1;
} else
break;
}
//判斷從a[i]到a[n]的每個數是否可以表示
for(int j=a[i]; j<=a[n]; ++j) {
if(visit[j-a[i]])
visit[j]=1;
}
}
cout<<ans<<'\n';
}
return 0;
} 、尋找道路find.cpp時空限制1000ms / 128MB
題目描述
在有向圖 G 中，每條邊的長度均為 1，現給定起點和終點，請你在圖中找一條從起點到終點的路徑，該路徑滿足以下條件：
路徑上的所有點的出邊所指向的點都直接或間接與終點連通。
在滿足條件1的情況下使路徑最短。
注意：圖 G 中可能存在重邊和自環，題目保證終點沒有出邊。
請你輸出符合條件的路徑的長度。
輸入格式：road.in
第一行有兩個用一個空格隔開的整數 n 和 m，表示圖有 n 個點和 m 條邊。
接下來的 m 行每行 2 個整數 x,y，之間用一個空格隔開，表示有一條邊從點 x 指向點y。
最後一行有兩個用一個空格隔開的整數 s, t，表示起點為 s，終點為 t。
輸出格式：road.out
輸出隻有一行，包含一個整數，表示滿足題目描述的最短路徑的長度。如果這樣的路徑不存在，輸出-1。
輸入輸出樣例
輸入樣例#1：
3 2
1 2
2 1
1 3
輸出樣例#1：
-1
輸入樣例#2：
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
輸出樣例#2：
3
說明
解釋1：
如上圖所示，箭頭表示有向道路，圓點表示城市。起點1與終點3不連通，是以滿足題目描述的路徑不存在，故輸出-1 。
解釋2：
如上圖所示，滿足條件的路徑為1- >3- >4- >5。注意點2 不能在答案路徑中，因為點2連了一條邊到點6 ，而點6不與終點5 連通。
【資料範圍】
對于30%的資料，0<n≤10，0<m≤20;
對于60%的資料，0<n≤100，0<m≤2000;
對于100%的資料，0<n≤10000,0<m≤200000,0<x,y,s,t≤n,x,s≠t。
【思路】：反向建圖從終點向起點用bfs删除掉相連的點，然後跑spfa
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=0x3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
struct node {
int to,next;
} edge[300006];
int n,m,bx,by,x,y,dis[300006],head[300006],visit[300006],flag[300006],sum;
void add(int u,int v) {
edge[++sum].next=head[u];
edge[sum].to=v;
head[u]=sum;
}
void spfa(int w) {
queue<int>q;
memset(visit,0,sizeof(visit));
memset(dis,maxn,sizeof(dis));
q.push(w);
dis[w]=0;
visit[w]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
visit[u]=0;
for(int i=head[u]; i; i=edge[i].next) {
int v=edge[i].to;
int z=1;
if(dis[v]>dis[u]+z&&flag[v]) {
dis[v]=dis[u]+1;
if(!visit[v]) {
visit[v]=1;
q.push(v);
}
}
}
}
}
void bfs(int by) {
queue<int>q;
memset(visit,0,sizeof(visit));
q.push(by);
flag[by]=visit[by]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u]; i; i=edge[i].next)
if(!visit[edge[i].to]) {
visit[edge[i].to]=1;
flag[edge[i].to]=1;
q.push(edge[i].to);
}
}
}
void begin_read() {
n=read();
m=read();
for(int i=1; i<=m; i++) {
x=read();
y=read();
add(y,x);
}
bx=read();
by=read();
}
void delete_edge() {
for(int i=1; i<=n; i++) {
if(!visit[i]) {
for(int j=head[i]; j; j=edge[j].next) {
int u=edge[j].to;
if(flag[u])
flag[u]=0;
}
}
}
}
int main() {
begin_read();
bfs(by);
for(int i=1; i<=n; i++) {
visit[i]=flag[i];
}
delete_edge();
spfa(by);
if(dis[bx]<=maxn)
printf("%d",dis[bx]);
else
printf("-1");
return 0;
} 轉載于:https://www.cnblogs.com/pyyyyyy/p/10788780.html