博客

用搜索超时 O(2^n)

 #include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int N,V,ans;
struct Data
{
  int d;
  int w;
};
Data f[1002];
void DFS(int cur,int L,int R,int res,int Fw)
{   
    Fw-=f[cur].w;
    if(Fw<=0)  {if(ans>res) ans=res;return;}   
    if(res>=ans) return;
    if(L>0)  DFS(L,L-1,R,res+Fw*(f[cur].d-f[L].d),Fw);
    if(R<=N) DFS(R,L,R+1,res+Fw*(f[R].d-f[cur].d),Fw);
}
int main()
{
 while(~scanf("%d",&N))
   {
    ans=0x7fffffff;
    scanf("%d",&V);
    int Fw=0,t;
    for(int i=1;i<=N;i++)
    {scanf("%d%d",&f[i].d,&f[i].w);Fw+=f[i].w;}
    DFS(V,V-1,V+1,0,Fw);
    printf("%d\n",ans);
   }     
}        

也算是dp吧

dp[L][R][0] 表示区间[L,R]的灯已关且卡多在位置L上

dp[L][R][1] 表示区间[L,R]的灯已关且卡多在位置R上

很容易得到:

dp[L][R][0]=min(dp[L+1][R][0]+effort(L,L+1),dp[L+1][R][1]+effort(R,L));

dp[L][R][1]=min(dp[L][R-1][0]+effort(L,R),dp[L][R-1][1]+effort(R-1,R));

effort(i,j) 为从点 i 移到点 j 所有灯所耗费的能量

特别注意的是:边界条件

由于是从点V开始,则要先把每个点到V的值求出,否则则会有 dp[V][V+1][0]=dp[V+1][V+1][0]这样的状态

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int N,V,ans;
struct Data
{
  int d;
  int w;
};
Data f[1002];
int dp[1002][1002][2];
int Sw[1002][1002];
int Fw;
int main()
{
 while(~scanf("%d",&N))
   {
    ans=0x7fffffff;
    scanf("%d",&V);
    Fw=0;
    for(int i=1;i<=N;i++)
    {scanf("%d%d",&f[i].d,&f[i].w);Fw+=f[i].w;
    }
    memset(Sw,0,sizeof(Sw));
    for(int i=1;i<=N;i++)
        for(int j=i;j<=N;j++)
            Sw[i][j]=Sw[i][j-1]+f[j].w;
    for(int i=V-1;i>0;i--)
    {
        dp[i][V][0]=dp[i+1][V][0]+(Fw-Sw[i+1][V])*(f[i+1].d-f[i].d);
        dp[i][V][1]=dp[i][V][0]+(Fw-Sw[i][V])*(f[V].d-f[i].d);
    }
    for(int i=V+1;i<=N;i++)
    {   
        dp[V][i][1]=dp[V][i-1][1]+(Fw-Sw[V][i-1])*(f[i].d-f[i-1].d);
        dp[V][i][0]=dp[V][i][1]+(Fw-Sw[V][i])*(f[i].d-f[V].d);
    }
    for(int L=V-1;L>0;L--)
        for(int R=V+1;R<=N;R++)
        {
         dp[L][R][0]=min(dp[L+1][R][0]+(Fw-Sw[L+1][R])*(f[L+1].d-f[L].d),
                                  dp[L+1][R][1]+(Fw-Sw[L+1][R])*(f[R].d-f[L].d));
         dp[L][R][1]=min(dp[L][R-1][0]+(Fw-Sw[L][R-1])*(f[R].d-f[L].d),
                                  dp[L][R-1][1]+(Fw-Sw[L][R-1])*(f[R].d-f[R-1].d));        
        }
    printf("%d\n",min(dp[1][N][0],dp[1][N][1]));
   }     
}