58 条题解
-
2
猫粮寸断 LV 10 @ 2018-11-01 19:45:21
//一道二进制枚举的题目，二进制的每一位表示一个团队选或者不选，用前缀和维护每一站的人数，所有站人数均不超则该方案可行 //总复杂度O(n*2^m) #include<iostream> using namespace std; int a[20],b[20],t[20],sum[20],dp[1<<18]; int main() { int n,m,v,i,j; long long mo,ans=0; cin>>n>>m>>v; for(i=0;i<m;i++) cin>>a[i]>>b[i]>>t[i]; for(i=0;i<(1<<m);i++) { mo=0; for(j=0;j<m;j++) if(i&(1<<j)) { sum[a[j]]+=t[j]; sum[b[j]]-=t[j]; mo+=(b[j]-a[j])*t[j]; } for(j=1;j<=n;j++) { sum[j]+=sum[j-1]; if(sum[j]>v) break; } if(j>n) ans=max(ans,mo); for(j=1;j<=n;j++) sum[j]=0; } cout<<ans; return 0; } -
1
Sky1231 (sky1231) LV 10 @ 2020-12-14 12:42:25
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <vector> #include <deque> using namespace std; namespace dts { typedef long long ll; ll n,m,v,a[1<<6],b[1<<6],t[1<<6],sum[1<<6]; int check() { for (ll i=0,tmp=0;i<n;i++) { tmp+=sum[i]; if (tmp>v) return 0; } return 1; } void main() { scanf("%lld%lld%lld",&n,&m,&v); for (ll i=0;i<m;i++) scanf("%lld%lld%lld",&a[i],&b[i],&t[i]); ll ans=0; for (ll i=0;i<(1<<m);i++) { ll tmp=0; memset(sum,0,sizeof(sum)); for (ll j=0;j<m;j++) if (i&(1<<j)) { sum[a[j]-1]+=t[j]; sum[b[j]-1]-=t[j]; tmp+=(b[j]-a[j])*t[j]; } if (check()) ans=max(ans,tmp); } printf("%lld\n",ans); } }; int main() { dts::main(); } -
1
直接枚举+模拟就行
//O(n*2^m) #include<iostream> #include<cstring> #include<algorithm> using namespace std; int n,s[20],v,m,a[20]; struct st{ int a,b,t; }e[20]; int main(){ cin>>n>>m>>v; int i,k,cn,p,ans=0,t; for(i=1;i<=m;i++){ cin>>e[i].a>>e[i].b>>e[i].t; } cn=1<<m; for(k=0;k<cn;k++){ //二进制数表示枚举状态,用t保存当前答案,s做前缀和检查是否符合要求 memset(a,0,sizeof(a)); p=k; t=0; for(i=1;i<=m;i++){ if(p&1){ a[e[i].a]+=e[i].t; a[e[i].b]-=e[i].t; t+=e[i].t*(e[i].b-e[i].a); } p>>=1; } s[0]=0; for(i=1;i<=n;i++) { s[i]=s[i-1]+a[i]; if(s[i]>v){ t=0; break; } } ans=max(ans,t); } cout<<ans; return 0; } -
0
明明是DFS，硬说是模拟。。。
编译成功foo.cpp:6:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable:4996)测试数据 #0: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 728 KiB, score = 10
Accepted, time = 0 ms, mem = 732 KiB, score = 100
c++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 18
#pragma warning (disable:4996)
using namespace std;
int nN, nM, nV, nMax;
struct tNode
{
int nFrom, nTo, nP;
}tPass[MAXN];
bool bMyCmp(const tNode &tA, const tNode &tB);
void vDfs(int nAi, int nCost,int nVis[]);
bool bCheck(int nVis[], tNode tA);
void vAdd(int nVis[], tNode tA);
int main()
{
int i, nVis[MAXN];
while (~scanf("%d%d%d", &nN, &nM, &nV))
{
for (i = 0; i < nM; i++)
scanf("%d%d%d", &tPass[i].nFrom, &tPass[i].nTo, &tPass[i].nP);
sort(&tPass[0], &tPass[nM], bMyCmp);
memset(nVis, 0, sizeof(nVis));
nMax = 0;
vDfs(0, 0, nVis);
printf("%d\n", nMax);
}
return 0;
}
bool bMyCmp(const tNode &tA, const tNode &tB)
{
if (tA.nFrom == tB.nFrom)
return tA.nTo < tB.nTo;
return tA.nTo < tB.nTo;
}
void vDfs(int nAi, int nCost, int nVis[])
{
int i, nT[MAXN], j;
if (nCost > nMax)
nMax = nCost;
for (i = nAi; i < nM; i++)
{
if (bCheck(nVis, tPass[i]))
{
for (j = 0; j < nN; j++)
nT[j] = nVis[j];
vAdd(nT, tPass[i]);
vDfs(i + 1, nCost + (tPass[i].nTo - tPass[i].nFrom)*tPass[i].nP, nT);
}
}
}
bool bCheck(int nVis[], tNode tA)
{
int i;
for (i = tA.nFrom; i < tA.nTo; i++)
{
if (i > nN)
return false;
if (nVis[i] + tA.nP>nV)
return false;
}
return true;
}
void vAdd(int nVis[], tNode tA)
{
int i;
for (i = tA.nFrom; i < tA.nTo; i++)
nVis[i] += tA.nP;
}
-
0
请高人指点，我为什么错了。。
var
i,j,n,k,x,v,m,sum,p:longint;
a,b,c:array [1..100] of longint;
f:array [1..100] of boolean;
procedure s(t:longint);
var
i,j:longint;
begin
if p>v then exit;
if k>sum then sum:=k;
if t=n+1 then exit
else
begin
for i:= 1 to m do
if b[i]<t then begin k:=k-(b[i]-a[i])*c[i]; p:=p-c[i]; f[i]:=true; end;
for i:= 1 to m do
if (b[i]>=t) and (f[i]) then
begin
f[i]:=false;
k:=k+(b[i]-a[i])*c[i];
p:=p+c[i];
s(t+1);
f[i]:=true;
p:=p-c[i];
k:=k-(b[i]-a[i])*c[i];
end;end;
end;begin
readln(n,m,v);
for i:= 1 to m do readln(a[i],b[i],c[i]);
fillchar(f,sizeof(f),true);
s(1);
writeln(sum);
end. -
0
chen199277 LV 10 @ 2009-11-09 16:23:16
注意上车时刻，和下车时刻。
到站时马上就下车了= =||害我wa了三次 -
0
prince_hao LV 10 @ 2009-10-18 21:02:14
program p1341;
type re=record
n,s,e:longint;
end;
var a,w,down:array[1..18]of re;
c:array[1..100]of boolean;
n,m,limit,ans:longint;
procedure init;
var i,j:longint;
begin
readln(n,m,limit);
for i:=1 to m do
readln(a[i].s,a[i].e,a[i].n);
end;
procedure sort;
var i,j:longint; t:re;
begin
for i:=1 to m do
for j:=i+1 to m do
if a[j].sn) then
begin
if sum>ans then ans:=sum;
exit;
end;
if pre0 then
for i:=1 to pre do
if (a[i].e>a[pre].s)and(a[i].e -
0
var
n,m,v,i,j,tt,ans:longint;
a,b,t,zz:array[1..18] of longint;procedure dfs(x,y:longint);
var
i,j,k:longint;
begin
if x>m then
begin
if y>ans then ans:=y;
exit;
end;if (t[x]a[j] then
begin
tt:=a[i]; a[i]:=a[j]; a[j]:=tt;
tt:=b[i]; b[i]:=b[j]; b[j]:=tt;
tt:=t[i]; t[i]:=t[j]; t[j]:=tt;
end;dfs(1,0);
writeln(ans);
end.
先按起点站大小排序，再搜索。 -
0
本菜的题解....
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 119ms
├ 测试数据 10：答案正确... 384ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：503ms
var
i,j,v,n,m,max,p:longint;
a,b,t,mm:array[1..18]of longint;
procedure writt;
var i,j,nv:longint;
f:boolean;
begin
nv:=0;f:=true;p:=0;
for i:=1 to n do
begin
for j:=1 to m do begin if (mm[j]=1)and(a[j]=i)then nv:=nv+t[j];if (mm[j]=1)and(b[j]=i)then nv:=nv-t[j];end;
if nv>v then f:=false;
end;
if f then for i:=1 to m do if mm[i]=1 then p:=p+(b[i]-a[i])*t[i];
if p>max then max:=p;
end;procedure doit(x:longint);
var i,j:longint;
begin
if x>m then writt
else
for i:=1 to 2 do
if i=1 then begin mm[x]:=1;doit(x+1);end else begin mm[x]:=0;doit(x+1);end;end;
begin
readln(n,m,v);
for i:=1 to m do
readln(a[i],b[i],t[i]);
max:=0;fillchar(mm,sizeof(mm),0);
doit(1);
writeln(max);
end.
猫粮寸断
LV 10
@ 2018-11-01 19:45:21
