头像

二助


访客:13043

离线:23小时前



二助
21天前

题目大意:

给你一个序列,问最少去掉多少个前缀元素能得到一个“好序列”。“好序列”是这样定义的:每次能从一个序列的左右两边取数,若能取出一个非递减序列则是“好序列”。

思路:

先分析什么样的序列能够叫做好序列,首先假设这个序列是b1,b2,…bm…bn。那么bm一定是最大的元素,然后从左到右是非减序列,从bm到bn是非增序列。为什么呢,假设b2<b1.那么你无论怎么取数b2一定在b1的后面形成递减的趋势,这是不被允许的。所以我们思路也很明确了,因为是去掉前缀,所以我们就找最长“好序列”,从后往前找,找到第一个不满足从后往前递增条件的元素,然后从这个元素往前找找到开始升的那个元素就停止,最后答案就是n减去最长“好序列”长度。

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        vector<int> a(n);

        for(int i=0;i<n;i++) cin>>a[i];

        int j=n-1;
        while(j>0 && a[j-1] >= a[j]) j--;
        while(j>0 && a[j-1] <= a[j]) j--;
        cout<<j<<endl;
    }

    //system("pause");
}



二助
22天前

题目描述:

给Alice一个带有N个数字的数组A [1…N]。
现在,Alice想通过参数K按照以下规则构建数组B:
最初,数组B为空。考虑数组A中的每个间隔。如果此间隔的长度小于K,则忽略此间隔。否则,在此间隔中找到第K个最大数字,并将此数字添加到数组B中。
实际上,Alice不在乎数组B中的每个元素。她只想知道数组B中的第M个最大元素。请帮助她找到这个数。

输入描述:

第一行是测试用例的数量。
对于每一个测试的情况下,第一行包含三个正数$N(1≤N≤10^5); K(1≤K≤N); M。$
第二行包含N个数甲$Ai(1≤Ai≤10^9)$。
保证M不大于数组B的长度。

输出描述:

对于每个测试用例,输出一行包含数组B中第M个最大元素的一行。

Sample Input

2
5 3 2
2 3 1 5 4
3 3 1
5 8 2

Sample Output

3
2

题解

  • 我们从下标为1的位置开始记录a[i] >= x的个数,当恰好有k个数大于等于x了(假设到下标i的时候恰好有k个数大于等于x了),那么区间[1,i]内一定能够作为一个区间,找到一个第K大数大于等于x

  • 那么我保持前面下标为1不动,向后一个一个的扩展,也一定能找到一个第K大的数大于等于x。

  • 即在区间[1,i],[1,i+1],[1,i+2],[1,i+3]…[1,n],这些区间都可以找到第K大的数大于等于x,即此时共有n-i+1个区间其第K大的数大于等于x。

17.PNG

那么只有这些吗?

  • 我们定义下标j,让j从头开始,即从1开始,往后移动,如果a[j] < x,那么这个数a[j]对于第K大的数是否大于等于x没有影响,因为它比x小,所以这个时候我们可以去掉它。
  • j往后移动一格,这样相当于起点变了,但是终点还是i,所以满足条件的区间还是[j,i],[j,i+1],[j,i+1]…[j,n],而且区间[j,i],[j,i+1],[j,i+1]…[j,n]中仍然有k个大于等于x的数,所以我们区间个数还是加上n-i+1,这个过程while循环即可,直到a[j] >= x停止,否则可以一直进行。

18.PNG

如果这个时候a[j]是一个大于等于x的数呢?

  • a[j] >= x,此时我们停止循环。
  • 我们要去掉这个数,从下一个开始,因此循环停止后,j++。
  • 大于等于x的个数要减1,这个时候,我们就得变化终点i了,i往后寻找到又一个第K大的数大于等于x的位置,重复上面的操作即可。

这样我们就可以求得第K大数大于等于x的区间一共有多少个。
如果个数大于等于M个说明我们枚举的x小了,否则我们枚举的x大了。

const int N=1e5+10;
int a[N];
int b[N];
int n,k;
LL m;

bool check(int x)
{
    LL res=0;
    int cnt=0;
    for(int i=1,j=1;i<=n;i++)
    {
        if(a[i] >= x) cnt++;
        if(cnt == k)
        {
            res+=n-i+1;
            while(a[j] < x)
            {
                res+=n-i+1;
                j++;
            }
            cnt--;
            j++;
        }
    }
   // cout<<"---"<<x<<' '<<res<<endl;
    if(res >= m) return true;
    else return false;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>k>>m;

        for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];

        sort(b+1,b+n+1);

        int l=1,r=n;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(check(b[mid])) l=mid;
            else r=mid-1;
        }

        cout<<b[l]<<endl;

    }

    //system("pause");
}


活动打卡代码 AcWing 419. FBI树

二助
24天前
string s;
int n;

void dfs(int l,int r)
{
    if(l == r)
    {
        if(s[l] == '1') cout<<'I';
        else if(s[l] == '0') cout<<'B';
        return;
    }

    int mid=l+r>>1;
    dfs(l,mid);
    dfs(mid+1,r);
    bool one=0,zero=0;
    for(int i=l;i<=r;i++)
        if(s[i] == '0') zero=1;
        else if(s[i] == '1') one=1;

    if(one && zero) cout<<'F';
    else if(!one && zero) cout<<'B';
    else if(one && !zero) cout<<'I';
}

int main()
{
    cin>>n>>s;
    dfs(0,s.size()-1);

    // system("pause");
}


活动打卡代码 AcWing 486. 等价表达式

二助
24天前
const int mod=13331;

stack<int> nums;
stack<char> opt;
int n;

string read()
{
    string s;
    char ch=getchar();
    while(ch == '\n' || ch == '\r' || ch == ' ') ch=getchar();
    while(ch != '\n' && ch != '\r')
    {
        if(ch != ' ') s+=ch;
        ch=getchar();
        if(ch == EOF) break;
    }
    return s;
}

void init()
{
    while(nums.size()) nums.pop();
    while(opt.size()) opt.pop();
}

inline int grade(char c)
{
    if(c == '+' || c == '-') return 1;
    if(c == '*' || c == '/') return 2;
    if(c == '^') return 3;
    return 0;
}

void calc(char op)
{
    int b=nums.top();nums.pop();
    int a=nums.top();nums.pop();
    if(op == '+') nums.push((a+b)%mod);
    if(op == '-') nums.push(((a-b)%mod+mod)%mod);
    if(op == '*') nums.push(a*b%mod);
    if(op == '^')
    {
        int res=1;
        while(b--) res=res*a%mod;
        nums.push(res);
    }
}

int check(string s,int x)
{
    init();

    nums.push(0);
    for(int i=0;i<s.size();i++)
    {
        if(s[i] == ' ') continue;
        if(s[i] >= '0' && s[i] <= '9')
        {
            int t=0,j=i;
            while(s[j] >= '0' && s[j] <= '9')
            {
                t=t*10+s[j]-'0';
                j++;
            }
            nums.push(t);
            i=j-1;
        }
        else if(s[i] == 'a') nums.push(x);
        else if(s[i] == '(') opt.push('(');
        else if(s[i] == ')')
        {
            while(opt.size() && opt.top() != '(')
                calc(opt.top()),opt.pop();
            if(opt.size() && opt.top() == '(') opt.pop();
        }
        else
        {
            while(opt.size() && grade(s[i]) <= grade(opt.top()))
                calc(opt.top()),opt.pop();
            opt.push(s[i]);
        }
    }

    while(opt.size() && opt.top() != '(')
        calc(opt.top()),opt.pop();
    return nums.top();
}

bool cmp(string a,string b)
{
    for(int i=0;i<1000;i++)
        if(check(a,i) != check(b,i))
            return false;
    return true;
}

int main()
{
    string exp;
    exp=read();

    cin>>n;

    for(int i=0;i<n;i++)
    {
        string line;
        line=read();
        //cout<<line<<endl;
        if(cmp(exp,line)) cout<<char('A'+i);
    }
    cout<<endl;
    // system("pause");
}



二助
26天前

Description

你是在离岛邮局工作的程序员。你所居住的地区,由多个岛屿组成。每个岛屿都有一个或多个港口城市。除了它们之外,还可能有其他城镇或村庄。要想从一个岛屿驶往另一个岛屿,就必须使用船只。要在一个岛屿中转,可以使用陆路,但是,有时使用海路更快。

以近年来进行的邮局私有化为契机,为了削减经费,在全国范围内进行了邮递员的人员整理。离岛的邮局也不例外,结果邮递员只有利藤先生一个人。由于该邮局负责集配的地域非常广,一个人集配是一项艰巨的工作。所以,利藤先生一直在向你求助,如何才能有效地进行集配呢?

你的工作就是在给出利藤先生应该追溯的城镇和村庄的集配顺序时,写出寻求最短巡回路线的程序。

利藤先生决不能在指定的顺序以外办理集配业务。但是,在从一个城镇或村庄移动到另一个城镇或村庄时,获准经由其他城镇或村庄进行移动。此外,利藤先生还拥有一艘船只,用来绕岛而行。?

例如,在被赋予了城镇A、城镇B、村C的集配顺序的情况下,从A到B时经由哪个城镇或村都没有关系。此时,虽然经由村C也可以,但是为了遵守集配顺序,在去城镇B进行一次集配之后,必须再次访问村C进行集配。另外,从城镇A使用海路前往城镇B,从城镇B使用陆路前往村C时,将船放在城镇B中。因此,下次想使用海路时有必要返回城镇B。

也有在一个城镇或村庄中必须进行多次集配的情况。例如,可能会给出城镇A、村庄B、城镇C、村庄B这样的集配顺序。此时,从城镇A不追溯到村庄B而前往城镇C的情况下,不能在城镇C突然进行集配,因为最初的村B的集配没有结束。即使在城镇C完成集配后访问村B进行集配,也不会结束第一次村B的集配。

利藤先生首先一定会在某港口城市随船。由于利藤先生是资深人士,所以可以忽略流动时间以外的集配工作所花费的时间。此外,只有在最后一个城镇或村庄完成集配业务所需的时间才是问题,不用考虑把船送回原来位置返回邮局所需的时间。

输入

输入由多个数据集构成。各数据集的形式如下所示。
N M
x1 y1 t1 sl1
x2 y2 t2 sl2
xM yM tM slM
R
z1 z2 … zR
数据集中的输入项目,均为非负整数。行中输入项目的分隔符为空白一个。

第一行,规定陆路及海路网的大小。

N(2≤N≤200)是城镇或村庄的数量。在每个城镇或村庄,从1~N分配到为止的固有号码。M(1≤M≤10000)是陆路和海路的合计条数。

从第2行开始1+M行是陆路或海路的记述。xi,yi(1≤xi, yi ≤ N)表示两端城镇或村庄的编号。ti(1≤ti≤1000)表示其陆路或海路的移动时间。sli是‘L’或‘S’中的任意一个,L表示陆路,S表示海路。

有时存在两条或两条以上直接连接某两个城镇或村庄的陆路或海路。每条陆路或海路是双向的,即可以朝任何方向移动。

第M+2行的R(1≤R≤1000)表示利藤先生负责的集配单位的数量。第M+3行,集配单位的城镇和村庄编号zi(1≤zi ≤ N)以收集和分配的顺序R排着一个。

在初期状态下利藤和船都是港口城市z1存在。从初期状态到集配地点的城镇和村庄,一定可以用某种方法移动。

输入的结尾以包含以空格分隔的两个0的一行表示。

输出

对于输入的各数据集,按照给定的集配顺序求出利藤在城镇和村庄巡回所需的最短移动时间,输出到一行。

样例输入

3 3
1 2 5 L
1 2 7 S
2 3 11 S
3
1 2 3
5 5
1 2 15 L
2 3 10 L
4 5 7 L
1 3 30 S
3 4 100 S
5
1 3 5 4 1
0 0

输出样例

18
269

题解

floyd,dp

  • 先预处理海路和陆路的最短路
  • dp[i][j]表示到达第i个目的地时船停在j处时的最小值
  • 转移:枚举上个停船点k
    if k == j 则直接走陆路z[i-1]->z[i]
    if k != j 则先从z[i-1]走陆路到k(若z[i-1] == k ,则该花费为0),再从k走海路到j,最后从j走陆路到z[i]
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,double> PID;
const int INF=0x3f3f3f3f;
const LL LNF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=210,M=1010;
int dl[N][N];//陆路
int ds[N][N];//海陆
int a[M];//访问顺序
LL f[M][N];//dp[i][j]: 已经走了前i个地方,当前船停在j点的最短移动时间
int n,m,r;

void init()
{
    memset(dl,0x3f,sizeof dl);
    memset(ds,0x3f,sizeof ds);
    for(int i=1;i<=n;i++)
        dl[i][i]=ds[i][i]=0;
}

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dl[i][j]=min(dl[i][j],dl[i][k]+dl[k][j]),
                ds[i][j]=min(ds[i][j],ds[i][k]+ds[k][j]);
}

int main()
{
    while(cin>>n>>m)
    {
        if(!n && !m) break;

        init();

        while(m--)
        {
            int a,b,c;
            char t;
            cin>>a>>b>>c>>t;
            if(t == 'L')
                dl[a][b]=dl[b][a]=min(dl[a][b],c);
            else
                ds[a][b]=ds[b][a]=min(ds[a][b],c);
        }

        cin>>r;

        for(int i=1;i<=r;i++) cin>>a[i];

        floyd();

        memset(f,0x3f,sizeof f);
        f[1][a[1]]=0;

        for(int i=2;i<=r;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    if(j != k) f[i][j]=min(f[i][j],f[i-1][k]+dl[a[i-1]][k]+ds[k][j]+dl[j][a[i]]);
                    else f[i][j]=min(f[i][j],f[i-1][j]+dl[a[i-1]][a[i]]);

        LL ans=LNF;
        for(int i=1;i<=n;i++) ans=min(ans,f[r][i]);
        cout<<ans<<endl;
    }
    // system("pause");
}



二助
26天前

题目描述

寒假到了,n 头牛都要去参加一场在编号为 x 的牛的农场举行的派对,农场之间有 m 条有向路,每条路都有一定的长度。

每头牛参加完派对后都必须回家,无论是去参加派对还是回家,每头牛都会选择最短路径,求这 n 头牛的最短路径(一个来回)中最长的一条路径长度。

输入格式

第一行有三个整数,分别表示牛的数量 n,道路数 m 和派对农场编号 x。
接下来 m 行,每行三个整数 u, v, w 表示存在一条由 u 通向 v 的长度为 w 的道路。

输出格式

输出一行一个整数表示答案。

输入

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

输出

10

题解

单源最短路&单终点最短路
单终点最短路径其实就可以把所有的边反过来,直接就转换为单源最短路径了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,double> PID;
const int INF=0x3f3f3f3f;
const LL LNF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=1010;
int g[N][N];
int rg[N][N];
int dist[N];
int rdist[N];
bool vis[N];
int n,m,x;

void dijkstra(int g[][N],int dist[])
{
    memset(dist,0x3f,sizeof rdist);//不能用函数里面的d进行sizeof, 因为那是指针
    memset(vis,0,sizeof vis);
    dist[x]=0;

    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!vis[j] && (t==-1 || dist[t] > dist[j])) t=j;
        vis[t]=true;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
}

int main()
{
    cin>>n>>m>>x;

    memset(g,0x3f,sizeof g);
    memset(rg,0x3f,sizeof rg);

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=c;
        rg[b][a]=c;
    }

    dijkstra(g,dist);
    dijkstra(rg,rdist);

    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,dist[i]+rdist[i]);

    cout<<ans<<endl;
    // system("pause");
}



二助
26天前

Description

我们的城市有几个货币兑换点。让我们假设每一个点都只能兑换专门的两种货币。可以有几个点,专门从事相同货币兑换。每个点都有自己的汇率,外汇汇率的A到B是B的数量你1A。同时各交换点有一些佣金,你要为你的交换操作的总和。在来源货币中总是收取佣金。 例如,如果你想换100美元到俄罗斯卢布兑换点,那里的汇率是29.75,而佣金是0.39,你会得到(100 - 0.39)×29.75=2963.3975卢布。 你肯定知道在我们的城市里你可以处理不同的货币。让每一种货币都用唯一的一个小于N的整数表示。然后每个交换点,可以用6个整数表描述:整数a和b表示两种货币,a到b的汇率,a到b的佣金,b到a的汇率,b到a的佣金。 nick有一些钱在货币S,他希望能通过一些操作(在不同的兑换点兑换),增加他的资本。当然,他想在最后手中的钱仍然是S。帮他解答这个难题,看他能不能完成这个愿望。

Input

第一行四个数,N,表示货币的总数;M,兑换点的数目;S,nick手上的钱的类型;V,nick手上的钱的数目;1<=S<=N<=100, 1<=M<=100, V 是一个实数 0<=V<=$10^3$. 接下来M行,每行六个数,整数a和b表示两种货币,a到b的汇率,a到b的佣金,b到a的汇率,b到a的佣金(0<=佣金<=$10^2$,$10^{-2}$<=汇率<=$10^2$)

Output

如果nick能够实现他的愿望,则输出YES,否则输出NO。

样本输入

3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00

样本输出

YES

题解

spfa判正环

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,double> PID;
const int INF=0x3f3f3f3f;
const LL LNF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=110,M=210;
struct Node
{
    int v;
    double rate,cash;
};
vector<Node> g[N];
double dist[N];
int cnt[N];
bool vis[N];
int n,m,s;
double v;

bool spfa()
{
    queue<int> q;
    q.push(s);
    dist[s]=v;//初始化s位置的钱, 其他位置的钱为0

    while(q.size())
    {
        int t=q.front();
        q.pop();
        vis[t]=false;

        for(int i=0;i<g[t].size();i++)
        {
            Node j=g[t][i];
            int v=j.v;
            double w=(dist[t]-j.cash)*j.rate;
            if(dist[v] <  w)
            {
                dist[v] =  w;
                cnt[v]=cnt[t]+1;
                if(cnt[v] >= n) return true;
                if(!vis[v]) q.push(v),vis[v]=true;
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m>>s>>v;

    while(m--)
    {
        int a,b;
        double c1,c2,uc1,uc2;
        cin>>a>>b>>c1>>c2>>uc1>>uc2;
        g[a].push_back({b,c1,c2});
        g[b].push_back({a,uc1,uc2});
    }

    if(spfa()) puts("YES");
    else puts("NO");

    // system("pause");
}



二助
27天前

题意

给定n,要求找到一组a,b满足a+b=n且LCM(a,b)尽可能小。

题解

设 a,b 为两个解,假设 a≤b ,那么显然 lcm(a,b) 一定 ≥b。这里我们要构造 lcm(a,b)=b 的解

也就是说,a 可以整除 b ,这又等价于 a 整除 n 。要让 lcm(a,b) 尽可能小,相当于让 b 尽可能小也就是 a 尽可能大。

所以总结一下,要让 a 整除 n 并且 a 尽可能大,那就找 n 的最大的不等于 n的约数就好了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const LL LNF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

int n;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;

        if(n % 2 == 0)
        {
            cout<<n/2<<' '<<n/2<<endl;
            continue;
        }

        int ans=-1;
        for(int i=2;i*i<=n;i++)
            if(n % i == 0)
            {
                ans=max(ans,i);
                ans=max(ans,n/i);
            }

        if(ans == -1) ans=1;
        cout<<ans<<' '<<n-ans<<endl;
    }
    // system("pause");
}



二助
28天前
题意

一个道路网连接了N个城市(从1个城市到N个城市),可能有一条以上的道路连接一个城市和另一个城市。有些道路是有偿的。从城市Ai到城市Bi,有两种方式支付旅行费用: 在城市Ci提前支付pi(Ci可能不等于Ai); 出差后在城市Bi支付。它花费了Ri。

编写一个程序,从城市1到城市N找到一个最低成本的路线。

Input

输入的第一行包含N和m的值,下面的m行通过指定ai、bi、ci、Pi、Ri的值来描述一条路。同一行的相邻值由一个或多个空格分隔。所有值是整数,1≤m,N≤10 0≤R P≤≤100。

Output

文件中唯一的一行必须包含从城市1到城市的最小可能的花费。如果因为任何原因,旅行是不可能的,你应该把“不可能”这个词写出来。

Sample Input

4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50

Sample Output

110

题解

状态压缩+dijkstra

  1. dp[i][s]:=走到i点时的最优解,且此时走过的点状态为s
  2. 按照普通的DAG状态压缩的做法是错误的,因为这种做法只能使用于有向无环图。而题目中的图可能存在环,所以只能按照dijkstra来进行松弛操作的同时进行状态转移。
  3. 题目中的某个点可能经过多次
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const LL LNF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=15;
struct Edge
{
    int to;
    int c,p;
    int r;
};
struct Node
{
    int to;
    int s;
    int dis;
    bool operator>(const Node &W) const
    {
        return dis>W.dis;
    }
};
vector<Edge> g[N];
int dist[N][1<<10];
bool vis[N][1<<10];
int n,m;

void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<Node,vector<Node>,greater<Node> > heap;
    dist[0][1]=0;
    heap.push({0,1,0});

    while(heap.size())
    {
        Node t=heap.top();
        heap.pop();
        int u=t.to,s=t.s;

        if(vis[u][s]) continue;
        vis[u][s]=true;

        for(int i=0;i<g[u].size();i++)
        {
            Edge j=g[u][i];
            int v=j.to;

            for(int s=0;s<1<<n;s++)
                if(s>>u & 1)//枚举的状态必须包含u,但可能同时包含v。因为可能重复路径
                {
                    int ns=s | 1<<v;
                    if(dist[v][ns] > dist[u][s]+j.r)
                    {
                        dist[v][ns] = dist[u][s]+j.r;
                        heap.push({v,ns,dist[v][ns]});
                    }
                    if((s>>j.c & 1) && dist[v][ns] > dist[u][s]+j.p)
                    {
                        dist[v][ns] = dist[u][s]+j.p;
                        heap.push({v,ns,dist[v][ns]});
                    }
                }
        }
    }
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<m;i++)
    {
        int a,b,c,p,r;
        cin>>a>>b>>c>>p>>r;
        a--,b--,c--;
        g[a].push_back({b,c,p,r});
    }

    dijkstra();

    int res=INF;
    for(int s=0;s<1<<n;s++)
        res=min(res,dist[n-1][s]);

    if(res == INF) puts("impossible");
    else cout<<res<<endl;
    // system("pause");
}



二助
28天前

Description

在笛卡尔平面上给出了n个点。现在,你必须使用一些矩形,其两侧是平行的轴,以掩盖他们。每一点都必须覆盖。一个点可以被几个矩形覆盖。每个矩形应该包括至少两个点,包括那些落在它的边界上的点。矩形应具有整体尺寸。退化的情况下(矩形与零区)是不允许的。你将如何选择矩形,从而最大限度地减少他们的总面积?

输入

输入由几个测试用例组成。每个测试用例都从包含单个整数的一行开始。n(2≤)n≤15)。下一个n行包含两个整数x, y(−1,000≤x, y≤1,000),给出点的坐标。假定没有两点是相同的。最后一个测试用例中只有一个零。

输出

为每个测试用例在单独的行上输出矩形的最小总面积。

样本输入

2
0 1
1 0
0

样本输出

1

题解

状压dp
先预处理出所有的矩形,有n*(n-1)/2个。

然后将每个矩形所涵盖的点也处理出来。

dp[s]表示矩形覆盖点集合为 s 的时候的最小面积

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=20,M=120;
struct Node
{
    int s;
    int area;
}a[M];
PII p[N];
int f[1<<15];
int n;
int cnt;

inline int calc(PII a,PII b)
{
    int l=max(1,abs(a.first-b.first));
    int w=max(1,abs(a.second-b.second));
    return l*w;
}

inline bool check(PII a,PII b,PII c)
{
    return (a.first-c.first)*(b.first-c.first)<=0 && (a.second-c.second)*(b.second-c.second)<=0;
}

void init()
{
    cnt=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
        {
            Node t;
            t.s=0;
            t.area=calc(p[i],p[j]);
            t.s |= 1<<i,t.s |= 1<<j;

            for(int k=0;k<n;k++)
                if(check(p[i],p[j],p[k]))
                    t.s |= 1<<k;
            a[++cnt]=t;
        }
}

void print()
{
    for(int i=1;i<=cnt;i++)
    {
        cout<<bitset<6>(a[i].s)<<' '<<a[i].area<<endl;
    }
}

int main()
{
    while(cin>>n && n)
    {
        int x,y;
        for(int i=0;i<n;i++) cin>>p[i].first>>p[i].second;

        init();

        //print();

        memset(f,0x3f,sizeof f);
        f[0]=0;

        for(int s=0;s<(1<<n);s++)
            for(int i=1;i<=cnt;i++)
                f[s|a[i].s]=min(f[s|a[i].s],f[s]+a[i].area);
        cout<<f[(1<<n)-1]<<endl;
    }
    // system("pause");
}