动态规划

痛并不快乐着..

数位dp

HDU 3555

不要49

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL dp[20][3];
int digit[20];

LL dfs(int pos,int pre,int state,bool jud){
    //cout<<pos<<" "<<state<<endl;
    ///数位递归到0则返回
    if(pos==0)
        return 1;
    ///如果有数据就返回数据
    if(!jud&&dp[pos][state]!=-1)
        return dp[pos][state];

    LL ans=0;
    int ed=jud?digit[pos]:9;
    //cout<<ed<<endl;
    for(int i=0;i<=ed;++i){
        if(pre==4&&i==9)continue;
        ans+=dfs(pos-1,i,i==4,jud&&i==ed);
    }
    if(!jud){///不取上界时,可以取满
        dp[pos][state]=ans;
    }
    return ans;
}

///数字处理函数
LL cal(LL x){
    int pos=0;
    while(x){
        digit[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,0,true);
}

int main(){
    memset(dp,-1,sizeof(dp));
    int T;
    for(scanf("%d",&T);T;T--){
        LL n;
        scanf("%lld",&n);
        printf("%lld\n",n-cal(n)+1);
    }
    return 0;
}

HDU 2089

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1000000+7;
LL dp[20][3];
int digit[20];

LL dfs(int pos,int pre,int state,bool jud){
    //cout<<pos<<" "<<state<<endl;
    ///数位递归到0则返回
    if(pos==0)
        return 1;
    ///如果有数据就返回数据
    if(!jud&&dp[pos][state]!=-1)
        return dp[pos][state];

    LL ans=0;
    int ed=jud?digit[pos]:9;//这句是判断他的上界
    //cout<<ed<<endl;
    for(int i=0;i<=ed;++i){
        if(pre==6&&i==2)continue;
        if(i==4)continue;
        ans+=dfs(pos-1,i,i==6,jud&&i==ed);
    }
    if(!jud){///不取上界时,可以取满
        dp[pos][state]=ans;
    }
    return ans;
}

///数字处理函数
LL cal(LL x){
    int pos=0;
    //cout<<"tx: ";
    while(x){
        digit[++pos]=x%10;
        //cout<<x%10<<endl;
        x/=10;
    }
    return dfs(pos,0,0,true);
}

int main(){
    memset(dp,-1,sizeof(dp));
    LL n,m;
    while(~scanf("%lld%lld",&n,&m) && n+m){
        printf("%lld\n",cal(m)-cal(n-1));
    }
    return 0;
}

51nod 1055 最长等差数列

Type: 动态规划,双向DP,思维,技巧

题目

N个不同的正整数,找出由这些数组成的最长的等差数列。

例如:1 3 5 6 8 9 10 12 13 14
等差子数列包括(仅包括两项的不列举)
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
6 8 10 12 14

其中6 8 10 12 14最长,长度为5。

Input

第1行:N,N为正整数的数量(3 <= N <= 10000)。
第2 – N+1行:N个正整数。(2<= A[i] <= 10^9)

Output

最长等差数列的长度。

Input示例

10
1
3
5
6
8
9
10
12
13
14

Output示例

5

题解

数据范围可判是O(N^2)
一开始我一直在想如何把数字,即两个数之间的差用哈希存起来,来方便dp.
然后搜了题解发现是论文题.
被叫做LLAP问题
Length of the Longest Arithmetic Progressio

论文Link:

https://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/

论文解释

这道题可以转化为:

给与一个 排过序 的集合set,我们要求这个集合中的最长等差数列的长度.

标重点: 序列是已排好序的
我们设 dp[i][j] 为以下标 i 和 j 两个元素开头的等差序列最长长度.
我们可以创建一个浮标 j 作为等差数列的中间值

初始化一个 i=j-1,k=j+1.

1.如果 set[i]+set[k] < set[j]*2

k++

2.如果 set[i]+set[k] > set[j]*2

i–

如果 set[i]+set[k]=set[j]*2

则构成等差数列,我们只需要让

dp[i][j]=(dp[j][k]==0)?3:dp[j][k]+1

如果dp[j][k]=0的话,dp[i][j]直接=3就可以了,因为 i,j,k 三个刚好构成等差数列.否则等于 dp[j][k]+1

计算完以后 i–,k++ 继续计算其他以 j 为第二个点的等差数列

倒序计算,正序反过来即可

另外: 还可以 直接将 dp 数组初始化为 2(因为每个数的等差数列至少为2).
dp[i][j]=dp[j][k]+1

另外有一个小技巧: 如果int的取值范围不大,但是数组要开很大的时候,可以用 short int,比如这道题.

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn=10000;

short int dp[maxn][maxn];
int Num[maxn],ans,N;

int main(){
    while(~scanf("%d",&N)){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<N;++i){
            scanf("%d",&Num[i]);
        }
        sort(Num,Num+N);
        ans=0;
        for(int j=N-2;j>=1;--j){
            int i=j-1,k=j+1;
            while(k<N&&i>=0){
                if(Num[i]+Num[k]>2*Num[j]){
                    --i;
                }else if(Num[i]+Num[k]<2*Num[j]){
                    ++k;
                }else{
                    dp[i][j]=(dp[j][k]==0)?3:dp[j][k]+1;
                    ans=max(ans,(int)dp[i][j]);
                    --i;++k;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

51NOD 1241 特殊的排序

Type:动态规划,思维,最长等差数列(简化)

题目

一个数组的元素为1至N的整数,现在要对这个数组进行排序,在排序时只能将元素放在数组的头部或尾部,问至少需要移动多少个数字,才能完成整个排序过程?
例如:
2 5 3 4 1 将1移到头部 =>
1 2 5 3 4 将5移到尾部 =>
1 2 3 4 5 这样就排好了,移动了2个元素。

给出一个1-N的排列,输出完成排序所需的最少移动次数。

Input

第1行:1个数N(2 <= N <= 50000)。
第2 – N + 1行:每行1个数,对应排列中的元素。

Output

输出1个数,对应所需的最少移动次数。

Input示例

5
2
5
3
4
1

Output示例

2

题解

一开始会想到和逆序数有关,排序就是减少逆序数,所以会想到其中非逆序序列中最长的那个不用变化.

然后可以容易地证明剩余的数只需要移动一次即可到达正确的位置上

比如 12346587
可以发现最长等差整数序列是 12345 而我们需要 12345678
第一次: 1234587 6
第二次: 1234586 7
第三次: 1234567 8
OK,往数列前面放的也一样

那么我们的问题就是如何求最长等差数列(等差为1)了,

因为等差为1,所以我们不难想到:
dp[i] 为数字 i 的最长等差数列.
遍历Num[]数组的时候计算 dp 即可
dp[i]=dp[i-1]+1

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10;

int dp[maxn],N,Num[maxn],max_;

int main(){
    while(cin>>N){
        memset(dp,0,sizeof(dp));
        dp[0]=0;
        max_=1;
        for(int i=1;i<=N;++i){
            cin>>Num[i];
        }
        for(int i=1;i<=N;++i){
            dp[Num[i]]=dp[Num[i]-1]+1;
            max_=max(dp[Num[i]],max_);
            //cout<<i<<" "<<dp[Num[i]]<<endl;
        }
        cout<<N-max_<<endl;
    }
    return 0;
}

51nod 1201 整数划分

Type:DP,思维

题意

将N分为若干个不同整数的和,有多少种不同的划分方式,例如:n = 6,{6} {1,5} {2,4} {1,2,3},共4种。由于数据较大,输出Mod 10^9 + 7的结果即可。

Input

输入1个数N(1 <= N <= 50000)。

Output

输出划分的数量Mod 10^9 + 7。

Input示例

6

Output示例

4

题解

首先我们可以由

1+2+3+…+m=n 估算出 大概只有sqrt(2*n)个数字左右

我们设当前状态为 dp[i][j]

dp[i][j] 代表当前数字为 j ,被划分成了 i 部分.
状态转移推倒:

我们假设已知所有 dp 的划分数序列.

(1) 我们将 dp[i][j-i] 每个 划分数每个数字 +1 ,我们将得到 不存在1 的划分数.

(2) 我们将 dp[i-1][j-i] 每个 划分数每个数字(共 i-1 个) +1 ,我们将得到 不存在1 的且长度为 i-1 ,和为 j-1 的划分数,然后我们将 1 放到划分数中,即得到全部 有1 的划分数.

即 dp[i][j]=(dp[i][j-i]+dp[i-1][j-i])%mod

正确性证明:

假设已知 dp[i][j] 的全部序列.
我们只需要一直对每个数字 -1 就可以将所有序列置为 全0.

给一个例子自己倒着推一下也成立

组成1的 有 {1} 

组成2的 有 {2} 

组成3的 有 {1,2} {3}

组成4的 有 {1,3} {4}

组成5的 有 {1,4} {2,3} {5}

组成6的 有 {1,5} {2,4} {1,2,3} {6}

组成7的 有 {1,6} {2,5} {3,4} {1,2,4} {7}

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=50010;
const LL mod=1e9+7;
int N;
LL dp[330][maxn];

int main(){
    scanf("%d",&N);
    dp[1][1]=1ll;
    for(int i=2;i<=N;++i){
        for(int j=1;j<=(int)sqrt(2*i);++j){
            dp[j][i]=(dp[j][i-j]+dp[j-1][i-j])%mod;
        }
    }
    LL ans=0;
    for(int i=1;i<=(int)sqrt(2*N);++i) ans=(ans+dp[i][N])%mod;
    printf("%lld\n",ans);
    return 0;
}

51nod 1084 矩阵取数问题 V2

Type:DP,多路(进程)DP

题目

一个M*N矩阵中有不同的正整数,经过这个格子,就能获得相应价值的奖励,先从左上走到右下,再从右下走到左上。第1遍时只能向下和向右走,第2遍时只能向上和向左走。两次如果经过同一个格子,则该格子的奖励只计算一次,求能够获得的最大价值。

例如:3 * 3的方格。

1 3 3
2 1 3
2 2 1

能够获得的最大价值为:17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起点和终点的奖励只计算1次。

Input

第1行:2个数M N,中间用空格分隔,为矩阵的大小。(2 <= M, N <= 200)
第2 – N + 1行:每行M个数,中间用空格隔开,对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

Output

输出能够获得的最大价值。

Input示例

3 3
1 3 3
2 1 3
2 2 1

Output示例

17

题解

一开始的想法是先走一遍取最大值,然后回溯到起点,把走过的地方置为 0,然后WA= =,发现是行不通的,因为两次都是最有没办法保证全局最优.

然后搜了题解

这里用到多进程dp,即我们用 dp[step][j][k] 代表当前走了 step 步,第一个走的人在第 j行,第二个走的人在第 k行时最大的经过路径之和.

如果 j==k 时,即两个人当前路径点重合了.我们只需要随便选取一个加到记忆化数组中即可.

而当我们多路dp时,两个人来到当前状态的方向可能是

(1) 第一个人往下走,第二个人往下走
(2) 第一个人往下走,第二个人往右走
(3) 第一个人往右走,第二个人往下走
(4) 第一个人往右走,第二个人往右走

我们只需要在遍历到每个状态时,对以上四个状态找最大值加上两个人当前地点的数字即可

答案是dp[M+N][N][N]

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=210;
int N,M,A;
int mp[maxn][maxn],dp[2*maxn][maxn][maxn];

int main(){
    ///读题bug,N是行,第二个读入
    scanf("%d%d",&M,&N);
    for(int i=1;i<=N;++i){
        for(int j=1;j<=M;++j){
            scanf("%d",&mp[i][j]);
        }
    }
    ///枚举步数
    for(int i=2;i<=N+M;++i){
        ///枚举位于行数 i-j or k即为当前所处列(因为总步数为i(行数加列数和))
        for(int j=1;j<=N&&i-j>=0;++j){
            for(int k=1;k<=N&&i-k>=0;++k){
                ///分为四种情况,下下,下右,右下,右右
                if(k==j){
                    //下下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+mp[j][i-j]);
                    //下右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+mp[j][i-j]);
                    //右下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+mp[j][i-j]);
                    //右右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]+mp[j][i-j]);
                }else{
                    //下下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+mp[j][i-j]+mp[k][i-k]);
                    //下右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+mp[j][i-j]+mp[k][i-k]);
                    //右下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+mp[j][i-j]+mp[k][i-k]);
                    //右右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]+mp[j][i-j]+mp[k][i-k]);
                }
            }
        }
    }
    printf("%d\n",dp[N+M][N][N]);
    return 0;
}


51nod 1020 逆序排列

Type:DP,逆序数

题目

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。

1-n的全排列中,逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)
给出2个数n和k,求1-n的全排列中,逆序数为k的排列有多少种?
例如:n = 4 k = 3。

1 2 3 4的排列中逆序为3的共有6个,分别是:
1 4 3 2
2 3 4 1
2 4 1 3
3 1 4 2
3 2 1 4
4 1 2 3

由于逆序排列的数量非常大,因此只需计算并输出该数 Mod 10^9 + 7的结果就可以了。

Input

第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)
第2 – T + 1行:每行2个数n,k。中间用空格分隔。(2 <= n <= 1000, 0 <= k <= 20000)

Output

共T行,对应逆序排列的数量 Mod (10^9 + 7)

Input示例

1
4 3

Output示例

6

题解

考虑 dp[i][j] 表示 元素个数为 i 个时 逆序数为 j 的全排列个数为 dp[i][j] 个.

设当前元素为 N ,则 N 可以放在原来 N-1 个元素的任意全排列的 N-i(i∈[0,N)) 上的位置.

当 N 放在位置 N-i 上时,该排列的逆序数会增长 i (因为N最大,所以后面i个为逆序,前面为顺序),所以当我们想要找长度为 N ,逆序数为 k 的个数时,只需要找长度为 N-1 ,逆序数为 k-i 的全排列的个数即可.

所以 dp[N][k] = lambda(dp[N-1][k-i] | i∈[0,N))

复杂度为 O(k(N^2)) 会炸.

考虑优化:

① dp[N][k] = lambda(dp[N-1][k-i] | i∈[0,N))
② dp[N][k-1] = lambda(dp[N-1][k-1-i] | i∈[0,N))
①-②: dp[N][k]-dp[N][k-1] = dp[N-1][k]-dp[N-1][k-N]
dp[N][k]=dp[N-1][k]-dp[N-1][k-N]+dp[N][k-1]

得出递推公式:

① dp[i][j]=1 j=0
② dp[i][j]=dp[i-1][j]-dp[i-1][j-i]+dp[i][j-1]

由题目的约束条件:

逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)

故枚举逆序数只需要枚举到 i*(i-1)/2&&j\<20000即可
注意j-i不能<0

Code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[1010][20010];

void init(){
    for(int i=1;i<=1000;++i) dp[i][0]=1;
    for(int i=2;i<=1000;++i){
        for(int j=1;j<=i*(i-1)/2&&j<=20000;++j){
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod;
            if(j-i>=0)dp[i][j]=(((dp[i][j]-dp[i-1][j-i])%mod)+mod)%mod;
        }
    }
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        printf("%d\n",dp[n][k]);
    }
    return 0;
}

第八届ACM省赛 K CF

CF

sdut 3903

Time Limit: 1000MS
Memory Limit: 65536KB

Problem Description

LYD loves codeforces since there are many Russian contests. In an contest lasting for T minutes there are n problems, and for the ith problem you can get aiditi points, where ai indicates the initial points, di indicates the points decreased per minute (count from the beginning of the contest), and ti stands for the passed minutes when you solved the problem (count from the begining of the contest).
Now you know LYD can solve the ith problem in ci minutes. He can’t perform as a multi-core processor, so he can think of only one problem at a moment. Can you help him get as many points as he can?

Input

The first line contains two integers n,T(0≤n≤2000,0≤T≤5000).
The second line contains n integers a1,a2,..,an(0<ai≤6000).
The third line contains n integers d1,d2,..,dn(0<di≤50).
The forth line contains n integers c1,c2,..,cn(0<ci≤400).

Output

Output an integer in a single line, indicating the maximum points LYD can get.

Example Input

3 10
100 200 250
5 6 7
2 4 10

Example Output

254

题意

有 n 道题目,每一道题都有一个初始分值 ai ,每个单位时间这道题的分数便会减少 di ,而我们可以在 ci 时间内做出这道题而得到分数,求在时间 T 内最多可以获得的分数。

题解

首先可以感觉出这是道0-1背包问题,然后我们需要知道,当我们做题时,会一两个角度来选择题目,其一是选择做题速度最快的,其二是选择做分值降低速度最快的.那么我们的衡量标准就可以看成先做单位时间内做题最多的那道.
然后我们根据上述规则排一下序.
在用排序后的数组进行0-1背包.在背包过程中记录最大值,即为最后的结果.

#include<bits/stdc++.h>
using namespace std;
const int maxn=3000;

struct pro{
    int a,d,c;
    //按单位时间内减少分值排序
    bool operator <(const pro &pt)const{
        return 1.0*d/c>(1.0*pt.d/pt.c);
    }
};

int n,T;
pro p[maxn];
int dp[5010];
int main(){
    while(~scanf("%d%d",&n,&T)){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;++i){
            scanf("%d",&p[i].a);
        }
        for(int i=0;i<n;++i){
            scanf("%d",&p[i].d);
        }
        for(int i=0;i<n;++i){
            scanf("%d",&p[i].c);
        }
        sort(p,p+n);
        int mx=-1;
        for(int i=0;i<n;++i){
            for(int j=T;j>=0;--j){
                if(j>=p[i].c){
                    dp[j]=max(dp[j],dp[j-p[i].c]+p[i].a-j*p[i].d);
                }
                mx=max(mx,dp[j]);
            }
        }
        printf("%d\n",mx);
    }
    return 0;
}

AOJ DPL_3 B Largest Rectangle

Largest Rectangle

Given a matrix (H × W) which contains only 1 and 0, find the area of the largest rectangle which only contains 0s.

Input

H W
c1,1 c1,2 ... c1,W
c2,1 c2,2 ... c2,W
:
cH,1 cH,2 ... cH,W

In the first line, two integers H and W separated by a space character are given. In the following H lines, ci,j, elements of the H × W matrix, are given.

Output

Print the area (the number of 0s) of the largest rectangle.

Constraints

  • 1 ≤ H, W ≤ 1,400

Sample Input

4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

Sample Output

6

最大子矩阵(直方图)的变形.

首先需要把每一行都预处理成距离第0行的高度的表.然后每一行都相当于一个直方图,对每个直方图求可以围成的所有矩形面积,用maxv维护最大矩形的值.

例 处理前:
    0 0 1 0 0
    1 0 0 0 0
    0 0 0 1 0
    0 0 0 1 0

After 处理后:
    1 1 0 1 1
    0 2 1 2 2
    1 3 2 0 3
    2 4 3 0 4

Code:

#include<cstdio>
#include<stack>
#include<iostream>
#include<algorithm>
#define MAX 1400
using namespace std;

struct Rectangle { int height; int pos; };

int getLargestRectangle(int size,int buffer[]){
    stack<Rectangle> S;
    int maxv=0;
    //通过后一位向前面的计算
    //这里用到的DP大概是无参数getLargestRectangle里面的预处理
    //这里用到的更多是思维吧,对每一行进行计算,最后求出最大值.
    buffer[size]=0;

    for(int i=0;i<=size;++i){
        Rectangle rect;
        rect.height=buffer[i];
        rect.pos=i;
        if(S.empty()){
            S.push(rect);
        }else{
            if(S.top().height < rect.height){
                S.push(rect);
            }else if(S.top().height > rect.height){
                int target=i;
                while(!S.empty() && S.top().height >= rect.height){
                    Rectangle pre=S.top();S.pop();
                    int area=pre.height*(i-pre.pos);
                    maxv=max(maxv,area);
                    target=pre.pos;
                }
                rect.pos=target;
                S.push(rect);
            }
        }
    }
    //printf("\nmaxv: %d\n",maxv);
    return maxv;
}

int H,W;
int buffer[MAX][MAX];
int T[MAX][MAX];

int getLargestRectangle(){
    //预处理每个点离他最近的上边未被污染地板的高度
    for(int j=0;j<W;++j){
        for(int i=0;i<H;++i){
            if(buffer[i][j]){
                T[i][j]=0;
            }else{
                T[i][j]=(i>0)?T[i-1][j]+1:1;
            }
        }
    }
    /*
    例:
        0 0 1 0 0
        1 0 0 0 0
        0 0 0 1 0
        0 0 0 1 0

    After:
        1 1 0 1 1
        0 2 1 2 2
        1 3 2 0 3
        2 4 3 0 4
    */
    int maxv=0;
    //传入两个值 W,列数,处理后T[i]第i行的首地址
    for(int i=0;i<H;++i){
        maxv=max(maxv,getLargestRectangle(W,T[i]));
    }

    return maxv;
}

int main(){
    scanf("%d %d",&H,&W);
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j){
            scanf("%d",&buffer[i][j]);
        }
    }

    printf("%d\n",getLargestRectangle());
    return 0;
}

UVa 10859

【Topic Link】

Placing Lampposts

【题意】

给你一个n个点m条边的无向无环图,在尽量少的节点上放灯,使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。

在灯的总数最小的前提下,被两盏灯同时被照亮的边数应该尽量大。

【题解】

树形dp,Lrj P70。

这题教会了我一个很有用的技巧:有两个所求的值要优化,比如让a尽量小,b也尽量小

那么可以转化为让 M*a+b尽量小,其中M应该是一个比“a的最大值和b的最小值之差”还要大的数

最终的答案为ans/M, ans%M

回到这题,要求放的灯总数最小,被两盏灯同时照亮的边数尽量大。

因为每条边要么被一盏灯照亮,要么被两盏灯照亮,所以可以转换为:

求:放的灯总数量最少,被一盏灯照亮的边数尽量少。

就可以变成球 M*a+b 的最小值,a为放置的灯数量,b为被一盏灯照的边数

f[u][1]表示u点放灯时的整个子树最小值
f[u][0]表示u点不放灯时的整个子树最小值

如果u放,那么u个子结点可以选择放,也可以不放,选择其中较小的值。如果选的是不照,就要增加一条只有一个灯照的边

如果u不放,那么其子结点就必须选择要放,而且每条边都只有一个灯照

【Code】

github: UVa 10859.cpp

#include<bits/stdc++.h>
using namespace std;
int T,n,m,vis[2000][2],d[2000][2];
vector Graph[1010];

int dp(int i,int j,int f){
    if(vis[i][j]) return d[i][j];
    vis[i][j]=1;
    int& ans=d[i][j];

    ans=2000;
    for(int k=0;k<Graph[i].size();++k) 
        if(Graph[i][k]!=f) 
           ans+=dp(Graph[i][k],1,i); 
    if(!j && f>=0)  ans++;

    if(j || f<0){
        int sum=0;
        for(int k=0;k<Graph[i].size();++k) 
           if(Graph[i][k]!=f) 
              sum+=dp(Graph[i][k],0,i); 
        if(f>=0) sum++;
        ans=min(ans,sum);
    }
    return ans;
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;++i) Graph[i].clear();
        for(int i=0;i<m;++i){
            int x,y;
            scanf("%d%d",&x,&y);
            Graph[x].push_back(y);
            Graph[y].push_back(x);
        }
        memset(vis,0,sizeof(vis));
        int ans=0;
        for(int i=0;i<n;++i){
            if(!vis[i][0])///新的一棵树
                ans+=dp(i,0,-1);
        }
        printf("%d %d %d\n",ans/2000,m-ans%2000,ans%2000);
    }
    return 0;
}

玲珑杯 Round#18 C

【Topic Link】

1146 – 图论你先敲完模板

【题解】

首先我们可以想到一个简单的dp方程

dp[i]=min(dp[j]+2^(dis[i]−dis[j]))+a

1.然后我们发现这个如果dis[i]−dis[j]>30的时候,决策为从i到j分开走更划算.

所以我们可以从i-1往回(1)递推,如果某一点距离差大于30.则直接退出循环即可.

最终结果为dp[n].且结果需要用long long存.

【Source Code】
github: Round#18 C.cpp



#include<bits/stdc++.h>
#define fill(x) memset(x,0,sizeof(x))
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int maxn=100000+10;
int n;
long long dp[maxn],a,dt[100000+10];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%lld",&n,&a);
        for(int i=1;i<=n;++i){ 
            dp[i]=1000000000000000000; 
            scanf("%lld",&dt[i]); 
            for(int j=i-1;j>=1;--j){
                long long t;
                if(dt[i]-dt[j]>30)break;
                if(dp[j]!=1000000000000000000) t=dp[j];
                else t=0;
                dp[i]=min(dp[i],t+(1<<(dt[i]-dt[j]))+a);
            }
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}