TIOJ 1058 兩個數字

        由於某位大神的需要,半夜又重新打開電腦打了這篇,這是一個非常麻煩的判斷題

但是如果某些東西運用得當,可以省下不少功夫,在此,我就說說我的簡易作法給各位參考

        首先,題目的麻煩之處,在於小數點以下可能會超出double範圍,所以就得用類似大數的處理方法,而我的方法是先當作c++型字串的string 輸入再處理,以下是我的處理方法

1.利用stringstream轉成浮點數先來大略判定大小

2.要是無法分出大小,可知double可儲存的範圍內,必定相同,所以整數部分必相同,整數位數亦然

    所以從頭開始比較大小即可,而題目說兩數不會相同,所以無須判定相同情況

因此,就有以下的code
p.s. stringstream的清除 一定要ss.clear();和ss.str(""); 缺一不可

#include <bits/stdc++.h>
using namespace std;
string s1,s2;
stringstream ss;
int main(){
 while(cin>>s1>>s2){
  int d1,d2;
  ss<<s1;
  ss>>d1;
  ss.clear();
  ss.str("");
  ss<<s2;
  ss>>d2;
  if(d1>d2)
   cout<<s1<<'\n';
  else if(d2>d1)
   cout<<s2<<'\n';
  else{
   for(int j=0;;j++){
    if(s1[j]>s2[j]){
     cout<<s1<<'\n';
     break;
    }
    else if(s2[j]>s1[j]){
     cout<<s2<<'\n';
     break;
    }
   }
  }
 }
}

TIOJ 1007 燈泡問題

　　這題幾天前就ＡＣ了,但是今天回去看了我的code,發現我根本不知道我在寫什麼ＱＱ

所以我以後打算稍微記下來,不然忘記很痛苦欸,還讓我去看日劇放鬆一下

　　這題很明顯就是ＤＰ,由於數字範圍不大,開個二維陣列不是問題,所以直接開始想狀態和轉移方程

我的想法就很簡單,如果當前要求時間長度為k的答案（最長持續亮時間仍是n),

可以分開討論

1,最後一格是暗的＝＞條件為＂時間長度為k-1"（最長持續亮時間是n)

2,最後一格是亮的＝＞條件為＂時間長度為k-1　且　末端的最長持續亮時間是n-1＂

那麼來定義狀態

dp[x][y]是指　時間長度為x ,而末端的最長持續亮時間是y

轉移方程就會變成

dp[x][y]=dp[x-1][n]+dp[x-1][y-1];

而dp[x][0]就是dp[x-1][n];

而邊界條件呢？

dp[1][0]=1 由於末端不能亮（最長持續亮時間是0) 所以只能是暗的

dp[1][y]=2 for 1<=y<=n 亮或不亮皆可

這樣就解決了這題　時間複雜度是Ｏ(mn) 空間複雜度也是Ｏ(mn) 

可是是說空間好像可以壓縮欸,每次轉移都只有用到上一列的狀態

所以可以把列數省略掉　dp[m][n]變成　dp[n] 而空間變成Ｏ(n)

這樣　就有以下的code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll n,m;
ll dp[16];
int main(){
cin>>n>>m;
dp[0]=1;
for(int i=1;i<=n;i++){
dp[i]=2;
}
for(int i=2;i<=m;i++){
ll x=dp[n];
for(int j=n;j>0;j--){
dp[j]=x+dp[j-1];
}
dp[0]=x;
}
cout<<dp[n]<<'\n';
}